Demostrar que para cualquier grafo conexo, existe un cerrado de a pie que visita cada arista exactamente dos veces.

Question

Para que esto ocurra, cada vértice tiene que tener un grado. Dado que este es un grafo conexo, sabemos que esto debe ser verdadero.

¿Cómo se puede demostrar que el cerrado a pie visitas a cada arista exactamente dos veces? ¿La existencia de un sistema cerrado a pie significa que hay un ciclo de la gráfica?

Answer 1

@Daniel Schepler le da una excelente respuesta en el comentario anterior. Aquí es constructiva de la prueba.

Si un gráfico es conectado contiene un árbol de expansión. En que spanning tree, usted puede encontrar una ruta a pie que visitas cada arista exactamente dos veces: dibujar el árbol de expansión como un plano gráfico y caminar alrededor de ella, manteniendo siempre un borde en su derecho.

Cada uno de los árboles de borde es visitado exactamente dos veces.

Ahora agregue la falta bordes, uno por uno. Cada vez que se agrega un borde, se usa para añadir un desvío (ida y vuelta) a la caminata.

Cada uno de los árboles del borde es visitado exactamente dos veces.

Answer 2

Prueba por inducción sobre el tamaño (número de aristas) de la (finito) gráfica conectada $G.$

Deje $G$ ser conectado a un gráfico de tamaño $m.$ Asume que cada grafo conexo de tamaño de menos de $m$ ha cerrado paseo que recorre cada arista dos veces. Si $m=0$ $G$ se compone de un solo vértice y el trivial de a pie que hace el trabajo. Supongamos $m\gt0.$ Seleccione una arista $uv$ $G.$

Caso 1. $G-uv$ está conectado.

Por la hipótesis inductiva, $G-uv$ ha cerrado a pie $W$ que recorre cada arista dos veces. Inicio en $u;$ a pie en $uv$ $u$ $v;$sigue cerrada a pie $W,$ comenzando y terminando en $v;$ caminar de regreso a $u$ sobre el borde de la $uv.$

Caso 2. $G-uv$ está desconectado.

Deje $H_u$ ser el componente de $G-uv$ contiene $u,$ y deje $H_v$ ser el componente que contenga $v.$ Por la hipótesis inductiva, $H_u$ tiene un paseo $W_u$ que recorre cada arista twie, y $H_v$ tiene un paseo $W_v$ que recorre cada arista dos veces. Inicio en $u;$ siga el paseo $W_u$ $u$ $u;$ a pie en $uv$ $u$ $v;$seguir $H_v$ $v$ $v;$ $u$ sobre el borde de la $uv.$