Circuitos eulerianos. Demostrar que si cada arista de un grafo G se encuentra en un número impar de ciclos, G es euleriano.

Question

La pregunta que necesito responder es: Demostrar que si cada arista de un grafo G se encuentra en un número impar de ciclos, entonces G es Euleriano.

Me cuesta hacerme a la idea de esta pregunta. He encontrado una respuesta a la pregunta en otro sitio web, pero no entiendo muy bien cómo se explica. El enlace a esa fuente es https://www3.nd.edu/~dgalvin1/40210/40210_F12/40210H4_sols.pdf en la sección 1.4.2 5 si esto ayuda.

Entiendo que si puedes demostrar que todos los vértices son de grado par entonces has terminado ya que si es así el grafo es euleriano. Es que me pierdo en alguna parte de la explicación. Si alguien tiene alguna idea sobre el planteamiento que se da en el enlace o incluso otra forma de responder a la pregunta, se lo agradecería mucho.

Answer 1

Lemma: Si un grafo cumple que cada arista está en un número impar de ciclos entonces cada vértice del grafo tiene grado par.

Pruebas: Denotamos por $f(e)$ el número de ciclos que contienen aristas $e$ .

Elige un vértice $v$ cuántos ciclos contiene $v$ ?

Obsérvese que cada uno de estos ciclos contiene exactamente dos de las aristas adyacentes a $e$ .

Por lo tanto, el número de ciclos que contienen $v$ es igual $\frac{1}{2} \sum\limits_{e \text{ is an edge adjacent to }v} f(e)$ .

Esto implica que la suma es par. Y como cada sumando es impar esto implica que hay un número par de sumandos, por lo que el grado de $v$ es par.