The question I need to answer is: Prove that if every edge of a graph G lies on an odd number of cycles, then G is Eulerian.
I'm having trouble wrapping my head around this question. I've found an answer to the question on another website but I don't quite understand the way it is explained. The link to that source is https://www3.nd.edu/~dgalvin1/40210/40210_F12/40210H4_sols.pdf
under section 1.4.2 5 if this helps.
I understand that if you can prove that every vertex is of even degree then you are done since if this is the case the graph is Eulerian. I'm just getting lost in the explanation somewhere. If anyone has any insight into the approach given in the link or even another way to go about answering the question, I would greatly appreciate it.
Best Answer
Lemma: If a graph satisfies that every edge is in an odd number of cycles then every vertex of the graph has even degree.
Proof: We denote by $f(e)$ the number of cycles containing edge $e$.
Pick a vertex $v$, how many cycles contain $v$?
Notice each such cycle contains exactly two of the edges adjacent to $e$.
Therefore the number of cycles containing $v$ is equal $\frac{1}{2} \sum\limits_{e \text{ is an edge adjacent to }v} f(e)$.
This implies that the sum is even. And since every summand is odd this implies there is an even number of summands, so the degree of $v$ is even.