I am working on proving the theorem that,

For a connected multi-graph G, G is Eulerian if and only if every vertex has even degree. By Eulerian here, I mean a graph that has a Eulerian Circuit. In this question I am focused on the (=>) direction of the proof.

I am using the following Proof, which is as followed:

If G is Eulerian then there is an Euler circuit, P, in G. Every time a vertex is listed, that accounts for two edges adjacent to that vertex, the one before it in the list and the one after it in the list. This circuit uses every edge exactly once. So every edge is accounted for and there are no repeats. Thus every degree must be even.

How does the proof follow?

Edit: I figured it out.


There is no choice of exit edge involved here as we assume a fixed Euler circuit given. Of $v$ is a vertex of $G$ and is visited by the given Euler circuit $k$ times (and is not the starting=ending vertex of it), then this vertex is "entered" $k$ times and "left" $k$ times, and each time via a different edge. This accounts for $2k$ different edges incident with $v$, and on the other hand, it must account for all edges incident with $v$.

The starting vertex has one "extra" leave, the ending vertex an extra enter, so if the starting and ending vertex coincide, we still have even degree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.