Estoy en un callejón sin salida con la siguiente pregunta, Parece bastante simple, pero me parece que no puede ver.
Sea G un simple grafo no dirigido con un mínimo grado 3, demostrar que G contiene un ciclo par.
Gracias.
Respuestas
¿Demasiados anuncios?
Considerar la máxima camino de $P$ en el gráfico G. Vamos a ser $u_1u_2...u_k$. Por el maximality de la ruta de $P$, sabemos que todos los vecinos de $u_1$ pertenecen a {$u_2,u_3,...,u_k$}. Desde $3\leq \deg(u_1)$, vamos a $u_i,u_j$ ser dos vecinos de $u_1$ tal que $2<i<j$. Ahora es fácil mostrar que uno de los siguientes ciclos debe ser: $$u_1u_2..u_iu_1$$ $$u_1u_2..u_ju_1$$ $$u_1u_iu_{i+1}..u_{j-1}u_ju_1$$
Esto es porque la suma de las longitudes de los tres ciclos de $=(i)+(j)+(j-i)=2j$ es aún, por lo tanto es imposible que los tres longitudes son impares.
Tyler
Puntos
1
Sugerencia 1:
Encontrar un ciclo de $c$ $G$ y un camino de $\pi$ que conecta dos vértices de $c$ sin el uso de un borde de $c$. El camino se divide $c$ en dos ciclos de $c_1$$c_2$. Si tanto $c_1$ $c_2$ son impares ciclos, entonces los caminos $c_1 \setminus \pi$ $c_2 \setminus \pi$ son tanto o incluso a un extraño. Por lo tanto $c$ es en este caso.
Sugerencia 2: Con el fin de encontrar $c$ $\pi$ tomar la primera a todos los puentes. Luego de tomar cualquier ciclo en un componente que no es un ciclo.
