No es necesario que el gráfico esté compuesto únicamente por un ciclo, pero cada ciclo del gráfico debe ser un ciclo de longitud impar. Intenté una prueba contrapositiva, tratando de demostrar que si todos los vértices tienen un grado mayor o igual a 3, entonces un gráfico no contiene ningún ciclo impar, pero no llegué muy lejos con eso.
Respuestas
¿Demasiados anuncios?
Supongamos que $G$ sólo tiene ciclos de longitud impar y ningún vértice de grado inferior a 3. Es evidente que podemos suponer que $G$ tiene un componente conectado.
Dejemos que $C$ sea un ciclo y con alguna arista $e$ de $c$ a $d$ en $C$ .
Reclamación: $e$ no se encuentra en ningún otro ciclo $C'$ . En primer lugar, si $C'$ sólo se reúne $C$ en los vértices $c$ y $d$ entonces podemos formar un ciclo mayor pasando de $c$ a $d$ en $C$ y luego de $d$ a $c$ en $C'$ que tiene $\# C - 1 + \#C' - 1$ aristas, lo cual es par ya que esos dos ciclos son Impares, y eso es una contradicción. Así que se encuentran en al menos un punto. Dejemos que $f$ sea el primer punto de $C$ que alcanzamos siguiendo $C'$ . Esto nos permite obtener dos nuevos ciclos: seguir $c$ a $f$ en $C'$ entonces $f$ a $c$ en $C$ así como $c$ a $f$ en $C'$ entonces $f$ a $c$ en $C$ . Uno de estos dos debe tener una longitud uniforme porque entre ellos tienen $\#C + 2$ que es un número impar, y la única forma de obtener un entero impar como suma es cuando al menos uno de los dos enteros es impar (de hecho exactamente uno). Así que de nuevo tenemos una contradicción.
Así, el gráfico puede descomponerse en la colección de todos los ciclos en $G$ y estos ciclos se encuentran como máximo en un vértice. Se puede ver cómo esto da lugar a un nuevo gráfico $H$ al colapsar todos los ciclos en puntos. Ese gráfico debe ser un árbol, porque cualquier ciclo en él desciende claramente a un nuevo ciclo en $G$ Sin embargo, todos los ciclos de $G$ ya están representados. Además, las hojas de $H$ debe consistir en estos ciclos colapsados o de lo contrario corresponderían a una hoja real en $G$ un vértice de grado $1<3$ .
Toma un ciclo $C$ en $G$ correspondiente a una hoja del árbol $H$ . Por lo tanto, exactamente un vértice de $C$ también se encuentra en otro ciclo, pero ninguno de los otros vértices lo hace (de los cuales hay al menos 2). Entonces ninguno de los otros vértices puede tener otras aristas, y en particular tienen grado 2, sin embargo cada vértice en $G$ se supone que tiene un grado de al menos 3, que es nuestra contradicción final.
bof
Puntos
19273
Una versión ligeramente más fuerte: un grafo no trivial sin ciclos pares tiene al menos dos vértices de grado inferior a $3$ . ("No trivial" significa que el gráfico tiene más de un vértice).
Demostraré el contrapositivo: si un grafo no trivial tiene a lo sumo un vértice de grado inferior a $3$ , entonces tiene un ciclo par.
De hecho, demostraré que un grafo no trivial (simple finito) $G$ con como máximo un vértice de grado inferior a $3$ debe contener un gráfico theta es decir, un grafo formado por dos vértices distintos conectados por tres caminos (simples) internamente disjuntos. Entonces, dos de los tres caminos deben tener longitudes de la misma paridad, formando así un ciclo par.
Dejemos que $P=(v_1,v_2,\dots,v_n)$ sea un camino máximo en $G$ con $n\gt1$ . Al menos un extremo de $P$ tiene un grado de al menos $3$ . Podemos suponer que $v_1$ tiene un grado de al menos $3$ por lo que tiene al menos dos vecinos además de $v_2$ . Desde $P$ es una ruta máxima, todos los vecinos de $v_1$ debe estar en $P$ Así que $P$ tiene vecinos $v_2,v_i,v_j$ donde $2\lt i\lt j\le n$ . Ahora hay tres caminos internamente disjuntos desde $v_1$ a $v_i$ El camino: el camino $P_1=(v_1,v_i)$ el camino $P_2=(v_1,v_2,v_3,\dots,v_{i-1},v_i)$ y el camino $P_3=(v_1,v_j,v_{j-1},\dots,v_{i+1},v_i)$ .
Observación. También podemos demostrar que, para cualquier primo $p\gt2$ si un gráfico no trivial tiene como máximo un vértice de grado inferior a $3$ entonces tiene un ciclo cuya longitud es pas divisible por p . Como acabamos de demostrar, hay dos vértices conectados por tres caminos internamente disjuntos $P_1,P_2,P_3$ donde el camino $P_1$ tiene una longitud $1$ . Si los ciclos $P_1\cup P_2$ y $P_1\cup P_3$ ambos tienen longitudes divisibles por $p$ , entonces los caminos $P_2$ y $P_3$ tienen longitudes congruentes con $-1$ modulo $p$ y así el ciclo $P_2\cup P_3$ tiene una longitud congruente con $-2$ modulo $p$ y, por tanto, no es divisible por $p$ .
Jimmy Kritsalos
Puntos
6
Demostraremos la afirmación contrapuesta. En concreto, si todos los vértices tienen un grado mayor o igual a 3, entonces debe existir un ciclo par.
Dejemos que $x$ sea un punto final de un camino maximal. Sabemos que $x$ tiene un grado de al menos 3, por lo que está conectado con al menos otros tres vértices $u$ , $v$ y $w$ . Sabemos que estos tres vértices deben estar en el camino máximo. WLOG, deja que $w$ sea un vértice adyacente a $x$ en la trayectoria máxima.
Si la ruta de $x$ a $v$ a lo largo del camino máximo es de longitud impar, entonces sabemos que hay un ciclo par. En concreto, el camino desde $x$ a $v$ a lo largo de la trayectoria máxima más la arista $(x, v)$ formará un ciclo par. El mismo argumento es válido si el camino desde $x$ a $u$ a lo largo de la trayectoria máxima es de longitud impar. Por lo tanto, si el camino desde $x$ a $v$ o $x$ a $u$ es de longitud impar, tenemos un ciclo par.
De lo contrario, debe ser que el camino de $x$ a $v$ y el camino desde $x$ a $u$ a lo largo del camino máximo son ambos de longitud par. En este caso, debe ser que el camino desde $u$ a $v$ también es de longitud par. Añadiendo los bordes $(u, x)$ y $(x, v)$ hemos encontrado un ciclo de longitud uniforme.
Así, en todos los casos, si todos los vértices tienen grado mayor o igual a 3, existe un ciclo par.
