1
$\begingroup$

I wrote this proof for simple graphs. Any feedback is appreciated.


Theorem: A connected graph has an Euler circuit $\iff$ every vertex has even degree.

Proof:

$P \implies Q$, we want to show that if a connected graph $G$ has an Euler circuit, then all $v \in V(G)$ have even degree.

An Euler circuit is a closed walk such that every edge in a connected graph $G$ is traversed exactly once. We define $w = v_0, v_1, v_2, ... v_k$, such that $v_0 = v_k$, to be that Euler circuit in $G$ of length $k$.

We assume $|V(G)| > 0$.

Case 1, $0 < i < k$: Since all edges in $w$ will be traversed, but no edge can be traversed more than once, we reach $v_i$ via one edge $\{v_{i-1}, v_i\}$ and have to leave via another untraversed edge $\{v_i, v_{i+1}\}$, so $deg(v_i) = 2n$, where $n$ is equal to the number of times $v_i$ appears in $w$, for $0 < i < k$.

Case 2, $i \in {0, k}$: At the beginning of $w$, we traverse any edge incident to $v_0$, that is $\{v_0, v_1\}$. By definition of an Eulerian circuit, we also have to conclude the walk at the same vertex where we started, hence we reach $v_0 = v_k$ again via a different, $k$-th edge $\{v_{k-1}, v_k\}$. Every $n$ times we pass $v_0 = v_k$ before concluding the walk, Case 1 applies, hence $deg(v_0) = deg(v_k) = 2 + 2n$, which is even.

$Q \implies P$, we want to show the other direction, that is if all $v \in V(G)$ have even degree, then a connected graph $G$ has an Euler circuit.

Proposition $P(n)$: If $G$ is a connected graph with $n$ edges and all $v \in V(G)$ have even degree, then $G$ has an Euler circuit. We proceed by induction on $n$.

Base case $P(0)$: A connected graph without any edges has only one vertex $v$ with $deg(v) = 0$, therefore $P(0)$ is true.

For purpose of induction, we assume $P(n)$ is true.

Inductive step, $P(n + 1)$: Assume $G$ has $n+1$ edges. Since all $v \in V(G)$ have even degree, we know $G$ can't be a tree, so we can find a cycle $c = u_0, u_1, ..., u_i, ..., u_k$ of length $k$ in $G$.

If $k = |E(G)|$, we found an Eulerian circuit that visits all edges exactly once and are done.

Otherwise, remove all edges in $c$ from $G$. The resulting subgraph $G'$ might contain $s$ connected components $G'_j$ for $0 \leq j < s$.

We know that all vertices in $c$ have even degree, so any vertex in $G'_{j}$ that was adjacent to a vertex in $c$ will have an even number of edges removed, therefore the parity of all $v \in G'$ remains even. the Also, all $G'_j$ will have at most $n$ edges.

Therefore we can assume $P(n)$ for all $G'_j$, that means we can find a Eulerian walk $w_j$ in each $G'_j$.

Now reinsert the edges from $c$ into $G'$, reconstructing $G$. We walk all vertices in $c$, starting at any vertex $u \in c$. When we reach a vertex $u_i$ in $c$ for the first time and $u_i$ was part of a $G'_j$, we branch into $w_j$, follow that Eulerian walk $w_j$ until its end and continue to $u_{i+1}$. We do this for all $G'_j$ until we reach $u_k$.

This will form an Eulerian walk that visits all edges in $G$ exactly once.


I found the last part, where the cycle is re-inserted into the graph again quite hairy to describe properly, but leaving out superfluous details.

$\endgroup$
1
$\begingroup$

There are two parts of your proof that I would consider incorrect, leaving out important details (which I'm sure you were aware of, but didn't write down):

In the $P \implies Q$ direction, Case 2, you only show that $\deg v_0 \ge 2$, which doesn't mean that it's even: $17 \ge 2$ and $17$ is odd. What you really want to argue here is that we use edges out of $v_0=v_k$ once at the very beginning, once at the very end, and twice every time it appears in the middle of the walk (this part is identical to Case 1), for a total of $2n+2$ edges, which is even.

In the $Q \implies P$ direction, when you write

we branch into $w_j$, walk until we reach $u_i$ again and continue the walk

this will not generally produce an Eulerian tour at the end. The closed walk $w_j$ might visit $u_i$ many times, and if you continue along $c$ the first time you return to $u_i$, you might miss out on many edges in $G_j'$. Instead, what you should do in this step is walk the entirety of the closed walk $w_j$, starting at $u_i$ and therefore ending at $u_i$, and then continue along $c$ to $u_{i+1}$.


Aside from that, I just have a couple of comments on clarity.

First, when you begin your induction

Let $P(n)$ be the proposition that if all $v\in V(G)$ have even degree, then a connected graph $G$ has an Euler circuit. We induct on $n=|E(G)|$.

you're not really using the right form for $P(n)$: you haven't made it a statement that depends on $n$. What you really want to define $P(n)$ to be is the proposition that "If $G$ is a connected graph with $n$ edges and all $v \in V(G)$ have even degree, then $G$ has an Euler circuit." (This also avoids the problem that, within the statement, you talk about $V(G)$ before you've said what $G$ is.)

Second, I'm not sure $P(3)$ is the right base case. I'd actually go with $P(0)$ (a graph with one vertex and no edges is connected, all vertices have even degree, and it has a trivial closed walk) because in your induction step, when you delete the cycle $c$, you may well end up with plenty of components that $P(0)$ should apply to. (And if we have $P(0)$, we can use it to prove $P(3)$: remove the cycle of length 3, and you have three components with $0$ edges.)

Third, a minor nitpick: when you're combining all the cycles together, you should only take the closed walk of $G_j'$ the first time you reach a vertex $u_i \in c$ that is a part of $G_j'$. (This is obvious if you know what you're doing, but it needs to be said if you want to describe a correct algorithm.)


But overall, well done! This is a complicated proof to write, with lots of fiddly details (which I didn't fully appreciate myself before I had to teach a recitation on it last semester), and you did a good job hitting all the important points. Don't let the length of my comments make you think otherwise.

$\endgroup$
  • $\begingroup$ Thanks a lot for your detailed feedback! I feel guilty for the $P \implies Q$ - Case 2. I was pretty sure this would get called out, but I was indeed at a loss of words for how to describe it better, haha. Thanks, I like your description, that makes it clear why $v_0 = v_k$ will have even degree and not just degree at least 2. Also very good feedback for the other points, I need to be more exact. :-)) $\endgroup$ – Max Oct 9 '17 at 1:35
  • $\begingroup$ Today I found some time in my lunchbreak to incorporate your feedback. If you happen to have some time, can you have a look? Thank you again! $\endgroup$ – Max Oct 11 '17 at 5:26
  • $\begingroup$ Looks good to me! $\endgroup$ – Misha Lavrov Oct 11 '17 at 6:13

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.