3
$\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$ I just read the title, so sorry if I miss something, but the statement is wrong. There are semi-euler graphs, that work, too: Exactly two knots have odd degree. $\endgroup$ Mar 10, 2023 at 8:31

1 Answer 1

4
$\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$
3
  • $\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$
    – BMBM
    Oct 9, 2017 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$
    – BMBM
    Oct 11, 2017 at 5:26
  • $\begingroup$ Looks good to me! $\endgroup$ Oct 11, 2017 at 6:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .