Euler's Theorem

Euler's Theorem describes a condition to which a connected graph $G = (V(G), E(G))$ is Eulerian. We will look at a few proofs leading up to Euler's theorem.

We will go about proving this theorem by proving the following lemma that will assist us later on.

Lemma 1: If $G$ is a graph with $\delta(G) \geq 2$, then the graph G must contain a cycle.

• Proof: Recall that $\delta (G)$ refers to the minimum degree of a graph.

• Suppose we have a graph $G = (V(G), E(G))$ such that $\delta (G) ≥ 2$. Let's let $P$ be any maximal path in the graph $G$ (not necessarily the maximum path). The maximal path $P$ cannot be extended any further. So the vertices of graph $P$ are:

(1)

\begin{align} V(P) = \left\{ x_1, x_2, ... , x_n \right\} \end{align}

• But $P$ is a maximal graph, so all neighbours of the vertex $x_1$ are in the set $\{x_2, x_3, ..., x_n \}$. Since $\delta (G) \geq 2$, then the degree of all other vertices is at least $2$. So the vertex $x_1$ has at least two neighbours on the path $P$. A cycle can thus be formed using $x_1$ and $x_j$ where $x_j$ is any neighbour of $x_1$. $\blacksquare$

The image below gives a visual interpretation of the proof of Lemma 1 from above.

Since the minimum degree $\delta (G) ≥ 2$, the vertices $x_2, x_3, ... x_{n-1}$ satisfy this by the definition of being a maximal path. But $x_1$ and $x_n$ must also satisfy this, so there must exist some other edges (gray) in the graph $G$ otherwise $\delta (G) = 1$.

Lemma 2: A Graph $G$ where each vertex has an even degree can be split into cycles by which no cycle has a common edge.

• Proof: Suppose we have a graph $G = (V(G), E(G))$ where each vertex in $V(G)$ has an even degree. We can first form a cycle by starting at a vertex and traversing around the graph. Note that since all vertices have even degree, then when you enter a vertex from an edge, you are always able to exit from another edge. Since the graph $G$ has a finite number of vertices, we will eventually return to the vertex we started at. We will call this cycle $C_1$.

• We can now remove this cycle from the graph $G$ to obtain a subgraph of $G$. This subgraph may or may not be connected, but that doesn't matter. Every vertex of this subgraph will have an even degree because when we passed by a vertex, we subtracted 2 from the degree as we entered using one edge, and exited using another edge. Hence, the next cycle $C_2$ can be obtained in the same manner, and the process can be repeated until there are no edges left to traverse. All of the cycles $C_1$, $C_2$, …, $C_n$ do not share any edges. $\blacksquare$

To illustrate Lemma 2 let's look at the following graph:

Notice that the degree of each vertex is even, so we can apply what the lemma from earlier to obtain some cycles of the graph by starting at a vertex and traversing along the graph until we return to the vertex.

Clearly, no edge was ever repeated. We can easily see this by extracting the cycles individually:

We are now ready to prove Euler's Theorem.

Theorem 1 (Euler's Theorem): A connected graph $G = (V(G), E(G))$ is Eulerian if and only if all vertices in $V(G)$ have an even degree.

• We now have the necessities to prove Euler's theorem on Eulerian graphs. We will prove this theorem using mathematical induction.

• For a connected graph $G = (V(G), E(G))$, for each $m \geq 0$, let $S(m)$ be the statement that if $G$ has $m$ edges and all of the degrees of vertices in $V(G)$ are even, then the graph $G$ is Eulerian.

• Base Step ($m = 0$): $S(0)$ has no edges. Since the graph is connected, the only possibly way a connected graph can have no edges is that the graph is a single vertex, let's call it $x_1$. $\deg (x_1) = 0$, which is even, and is trivially Eulerian.

• Induction Step $S(0) \wedge S(1) \wedge ... \wedge S(k-1) \implies S(k))$: Let $k \geq 1$ and assume that $S(1), S(2), ..., S(k + 1)$ is true. We want to prove $S(k)$ is value. Let $G$ be a graph with $k$-edges, is connected, and all vertices of $G$ have even degrees.

• Since $G$ is a connected graph, there are no isolated vertices, so it follows that the smallest degree $\delta (G) ≥ 1$. But all degrees are even, so $\delta (G) ≥ 2$. From above, this graph $G$ must contain a cycle, let's call it $C$.

• Now let's create a new graph $H$ by removing all of the edges that are in graph $C$ from graph $G$. Note that the graph $H$ may be disconnected. We can say the graph $H$ is the union of the connected components $H_1, H_2, ..., H_t$. The degree is each $H_i$ must be even since the degrees drop only by $0$ or $2$.

• Applying the induction hypothesis to each $H_i$ that is $S( \mid E(H_1) \mid), ..., S( \mid E(H_t) \mid)$, each $H_i$ will have an Eulerian circuit, let's say $C_i$.

• We can now create a Eulerian circuit for $G$ by splicing together the graph $C$ with the $C_i$'s. First start on any vertex of $C_i$ and traverse until you hit some $H_i$. Then traverse $C_i$ and continue back on $C$ until you hit the next $H_i$.

• Conclusion: Thus it follows that $G$ must be Eulerian. This completes the inductive step as $S(0) \wedge S(1) \wedge ... \wedge S(k-1) \implies S(k))$. By the principle of strong mathematical induction, for $m \geq 0$, $S(m)$ is true. $\blacksquare$

Corollary 1: If a connected graph $G = (V(G), E(G))$ has $2m$ odd vertices, then $G$ can be traversed in $m$ strokes.

• Proof: Recall that adding a single edge between two vertices results in the degrees of both vertices increasing by $1$.

• For $m ≥ 1$, let $G = (V(G), E(G))$ be a connected graph with $2m$ odd vertices. Then we can created another graph, let's say $G^*$ by adding one edge between one of those pairs of odd vertices. Repeat this process until there are $0$ pairs of odd vertices. Thus we will need to add $m$ edges. $G^*$ will now be Eulerian since all vertices in $V(G^*)$ are even. Thus there must exist an Eulerian circuit. From this circuit, we can remove the $m$ new edges and hence the graph can be drawn in m strokes.

Theorem 2: A graph G that is connected is semi-Eulerian if and only if two vertices in the graph have odd degree.

• Proof: Let $G = (V(G), E(G))$ be a semi-Eulerian graph. Let vertices $x_1$ and $x_2$ be the start and end vertices of the Eulerian trail respectively, since one must exist by the definition of a semi-Eulerian graph. Adding an edge between $x_1$ and $x_2$ will result in a new graph, let's call it $G^*$, that is Eulerian since the degree of each vertex must be even. By removing that edge, the degrees of $x_1$ and $x_2$ must be odd as the removal of an edge results in decrementing the degree of $x_1$ and $x_2$ by $1$ each.

• Alternatively, let $G = (V(G), E(G))$ be a connected graph with exactly two vertices of odd degree, let's call them $x_1$ and $x_2$. By adding an edge to $x_1$ and $x_2$ then each vertex in $G$ has an even degree. Thus an Eulerian trail exists. The removal of this edge between $x_1$ and $x_2$ results in an open trail which contains all edges of $G$. Thus $G$ must be semi-Eulerian. $\blacksquare$