Eulerian Circuit

Bridges of Konisberg

This is essentially the origins of graph theory. The map is decomposed to the following graph:

$"\\begin{document}\n\\begin{tikzpicture}\n$

source code

Is there a trail that visits each edge once?

Definition (Eulerian Graph)

A Graph $G$ is called Eulerian if it contains a circuit that visits each edge of $G$ once (and has the same start and end. That circuit is called an Eulerian Circuit.

If we are talking about a trail, then the graph is called Semi-Eulerian and the trail is called an Eulerian Trail.

Since a circuit is a trail, then

$$\text{Eulerian}⟹\text{Semi-Eulerian}$$

Observations On Eulerian Graphs

• We note that if $G$ is Eulerian/Semi-Eulerian, it must be connected since there is no way to move between two connected components.
• In any circuit, if you enter a vertex, you must also leave it. For some vertex $v$, and edge that visits $v$ must have some edge that exits. In particular, each edge must come in pairs. Thus, if $G$ is Eulerian, then $\mathrm{deg}(v)$ must be even $\forall v\in V(G)$.
  • So, in the Bridges of Konisberg, we this graph cannot possibly be Eulerian, since $\mathrm{deg}(D)$ is odd.

Theorem (Eulerian Graphs have Even Degree)

A finite graph $G$ is Eulerian iff

1. $G$ is connected except for its isolated vertices and
2. all vertices of $G$ have even degree.

Proof: Let $G$ be Eulerian.

$(⟹)$ This is trivial. $(1)$ is immediate by definition of Eulerian, and two is from Observations On Eulerian Graphs.

$(⟸)$ We can ignore the isolated vertices, and only pay attention the singular connected component.

Claim A: $G$ has a circuit, or it is empty. This is obvious.

Claim B: The edges of $G$ can be partitioned into circuits.

We prove by strong induction. We only need to assume $(2)$, in that all vertices of $G$ have even degree. If $|E|=0$, then we are done (base case). Otherwise, we have some Cycle $C$.

If we repeatedly remove $E(C)$ from $E(G)$, then the degrees of the vertices are even. Indeed, each vertex in the cycle only has $2$ degrees, so we are only removing an even number of edges. Thus, $G\setminus C$ satisfies $(2)$. The vertices have $0$ or $2$ edges of $C$.

By the inductive hypothesis, we can partition the edges into cycles, and we have proven B.

The reason we use strong induction here is because when we remove the first cycle $C$, we want to be able to reason that $G\setminus C$, of some $n-k$ edges also satisfies the inductive hypothesis (as opposed to weak induction only allowing us to reason the next number/iteration).

Claim C: We can merge cycles together to form a circuit. Given two cycles, $C_1,C_2$, have no common edges, but they have a common vertex.

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

where $C_1$ is a circuit, and $C_2$ is another (ignore that the colors don’t match). You can think of the circuits at loop that

• $C_1:v\to v$
• $C_2:v\to v$
• $C_1+C_2:v\stackrel{C_1}{\to }v\stackrel{C_2}{\to }v$ We have created a single circuit $C_1+C_2$ that uses all of their edges. Thus, C is proven.

Claim D: If $G$ is connected and its edges are partitions into some circuits $C_1,C_2,\dots ,C_n$, then $G$ is Eulerian. We prove this by induction on $n$.

If $n=1$, then we are done.

Note that $C_n$ should share some vertex with $C_i$ with $1\le i\le n$. If not, $G$ would be disconnected, a contradiction. Let $C^{\prime }$ be this circuit using the edges of $C_i$ and $C_n$. So our path

$$E=C_1\cup \cdots \cup C_i^{\prime }\cup \cdots \cup C_{n-1}$$

with our partition $E$ as our set of edges. Essentially, at each step we apply C and keep merging to a larger circuit until $E$ is just $E(G)$. By our inductive hypothesis, $G$ is Eulerian since we now have a Eulerian trail over the entire graph.

Theorem (Semi-Eulerian Can Have Odd Degrees)

A finite $G$ is Semi-Eulerian iff

1. $G$ is connected except for isolated vertices
2. $G$ has at most $2$ vertices of odd degree.

Proof:

$(⟹)$ Suppose $G$ had an Eulerian trail that starts at $u$ and ends at $v$. If this is true, then if we add an edge $e=(u,v)$, our trail is now a circuit since the start and end are the same.

If $G$ has a $u-v$ Eulerian trail (and thus Semi-Eulerian), then $G\cup \{u,v\}$ is Eulerian. By Theorem (Eulerian Graphs have Even Degree), $G$ is connected except for isolated vertices, proving $(1)$. If we call this graph $G^{\prime }$, then $G^{\prime }$ has even degrees. Upon removal of edge $(u,v)$, every vertex of $G$ except $u,v$ has an even degree, proving $(2)$.

$(⟸)$ We have cases on the number of odd degree vertices.

• If there are zero, then $G$ is Eulerian, and thus Semi-Eulerian by definition of a circuit.
• If there is one odd degree vertex, then this is impossible by the Handshake Lemma, since we would have an odd sum of edges.
• If we have two odd degree vertices, $u,v$, let $G^{\prime }=(E(G)\cup \{e\},V(G))$ where $e=(u,v)$. $G^{\prime }$ has all even degree and is connected. By Theorem (Equivalent Eulerian), $G^{\prime }$ is Eulerian. Then $G^{\prime }$ has a circuit that ends at with edge $e$, then removing it gives us an Eulerian trail, and so $G$ is Semi-Eulerian.

Alternative, Constructive Proof of Theorem

We can try to build a trail as we go. $G$ has an Eulerian trail that starting at some vertex $u$ iff

• all the edges of $G$ connect to the vertex $u$,
• at most one vertex other than $u$ has an odd degree.

Say we took some edge $e=(u,w)$ as the start of our trail for some graph $G$. Obviously, the next edge must be incident with $w$. In particular, we want to prove graph $G^{\prime }$ ($G$ without $e$) should have an Eulerian trail starting at $w$.

So, is true if

1. at most one vertex other than $u$ has an odd degree in $G^{\prime }$.
2. $G^{\prime }$ is connected to all edges in $G^{\prime }$.

This should look similar to what we were proving initially.

Here, $(1)$ is automatic if the removal of $e$ caused $u,w$ to have degree decreased, and thus are now even (with the degrees of the other vertices are invariant. Otherwise, $G$ has odd degrees in $u$ and some other vertex $v$. After removal of $e$, then $G^{\prime }$ has odd degree at $w$ and some other vertex $v$. Unless of course, $v=w$ and $(1)$ holds.

For $(2)$, we cannot choose a bridge (unless $\mathrm{deg}(u)=1$). However, if $\mathrm{deg}(u)>1$ and there are at most one other odd degree vertex, then $u$ has a a non-bridge edge.

Suppose by contradiction $u$ has only bridges,

$"\\usepackage{tikz-cd}\n\\begin{document}\n\\begin{tikzcd}\n\t& {C_1} \\\\\n\t{C_2} & u & {C_3}\n\t\\arrow[no head, from=2-2, to=1-2]\n\t\\arrow[no head, from=2-2, to=2-1]\n\t\\arrow[no head, from=2-2, to=2-3]\n\\end{tikzcd}\n\\end{document}"$

source code

where $C_i$ are other connected parts of the graph. Then picking any edge will disconnect the graph. Suppose $G_i$ is the subgraph $C_i$ with $u$ and its edge to it. Then $G_i$ has an even number of odd degree vertices by the Handshake Lemma. In particular, an even number of odd degree vertices ensures $G$ has an even $|E|$ and thus an even ${\sum }_{v\in V(G{)}_i}\mathrm{deg}(v)$. But then $u$ is an odd degree.

But then this implies $C_i$ has some other odd degree vertex. But then $G_i$ has exactly one (an odd number!) vertex of odd degree, contradicting the Handshake Lemma.

Thus there must exist at least one edge that is not a bridge. By always choosing this edge, the graph of the remaining edges stays connected, allowing us to traverse every edge and complete the Eulerian trail.