Matemáticas discretas - Problema de teoría de gráficos

Question

Estoy tratando de hacer Matemáticas para el curso de CS( 6.042) del MIT opencourseware. Podría alguien ayudarme con este problema (del conjunto de problemas 6. Problema 6).

Sea G un gráfico. En este problema demostramos que cada vértice de grado impar está conectado con al menos otro vértice de grado impar en G.

(a) [6 pts] Sea v un nodo de grado impar. Considere el paseo más largo que comienza en v y que no repite ninguna arista (aunque puede omitir algunas). que no repite ninguna arista (aunque puede omitir alguna). Sea w el nodo final de ese paseo. Demuestre en que w no es igual a v.

(b) [4 pts] Demuestre que w también debe tener grado impar.

Answer 1

SUGERENCIA: Imagina que caminas a lo largo de ese paseo, eliminando cada arista del mismo a medida que avanzas. Cada vez que pases por un vértice (es decir, dentro de él y fuera de él), eliminas dos de las aristas de ese vértice. Utiliza esto para demostrar que si el vértice tenía un grado par originalmente, nunca puedes quedarte atascado allí: si el paseo te lleva al vértice, también debe sacarte de nuevo.

Answer 2

Pregunta 1: Prueba por contradicción

Supongamos que el w = v. Eso significa que en un paseo no queda ninguna arista que salga de v tal que podamos caminar por esa arista. Entonces, caminamos por todas las aristas que salen de v. Así, por cada vez que salimos de v, pudimos volver a v (porque w = v). Eso significa que v debe tener grado par. Llegamos a la contradicción porque v tiene grado impar. Por lo tanto, w no es igual a v.

Pregunta 2: Prueba por contradicción

Supongamos que w tiene grado par. Por lo tanto, el paseo termina en el nodo de grado par. A partir de w no podemos avanzar más porque todas las aristas han sido visitadas desde w. Pero cada vez que el paseo entra en w debe salir de w porque tiene grado par. Por lo tanto, en ese sentido la última arista del paseo entra en w y no sale. Entonces, antes de la última arista siempre que se llegó a w se salió, eso muestra que el grado par de w ha sido recorrido pero como la última vez que se entró a w no se salió. Por lo tanto, muestra w tiene grado impar. Por lo tanto llegamos a la contradicción