Prueba de que un gráfico tiene recorrido de Euler si cada vértice tiene grado par

Question

Esta es la prueba:

He podido entender esta prueba excepto la última parte. Consideran que el borde $\{u, v_i\}$ para demostrar que si $W$ no es el recorrido de Euler entonces tampoco es el paseo más largo, ya que se puede extender un nuevo paseo $W^{'}$ puede formarse. Sin embargo, afirman:

$W^{'}=u,v_i,v_{i+1},..., v_k, v_1, v_2,..., v_i $ y esto contradice nuestra afirmación de que cada nodo tiene grado par, ya que en este caso $v_i$ tiene el grado de impar. Entonces, ¿no es un error considerarlo? (Como $W^{'}$ ni siquiera es posible en nuestro escenario de nodos con grado par)

Answer 1

Obsérvese que para que haya una contradicción, lo que tenemos que demostrar es que no hay más camino que $W$ . Así que mientras se hace una suposición sobre $W'$ Sólo tenemos que elegir $W'$ tal que la longitud de $W'$ es más que $W$ . No asumimos $W'$ es el paseo más largo.

En otras palabras, podría haber otro paseo más corto, digamos $v_i, a_1, a_2,...,a_m$ que hace que el grado de $v_i$ incluso pero no la parte de la prueba ya que estamos asumiendo que hay un paseo más largo. En este caso, el paseo más largo puede sea $u,v_i,v_{i+1},..., v_k, v_1, v_2,..., v_i, a_1, a_2,...,a_m$ con $u = a_m$ (porque hay que tener un paseo cerrado para que sea el más largo). Mientras no asumamos $W'$ es el El más largo caminar, sino un más largo caminar, podemos tener grados de impar en él. Esa es la misma razón por la que la prueba tuvo que declarar $v_k = v_0$ para $W$ (ya que asumimos que es el El más largo ).