Eulerian tour theorem

This post looks at Eulerian cycle theorem in graph theory.

We first define a few terms.

A walk is an alternating sequence of vertices and edges, beginning and ending at a vertex with the constraint that each edge between two vertices must be incident on these two vertices. Essentially, it means moving in a graph along the edges in a continuous fashion. For example, a typical walk of length $n$ is of the form $$v_1 e_1 v_2 e_2 v_3 e_3 \cdots v_{n-1} e_{n-1} v_n e_n v_{n+1} \tag{$\star$}$$ where $e_j$ is incident to $v_j$ and $v_{j+1}$.

A cycle is a walk with the beginning and ending vertices being the same, i.e., $(\star)$ with $v_{n+1} = v_1$.

A walk where no edge is repeated is called a trail, i.e., $e_j \neq e_k$ for $j \neq k$ in $(\star)$.

A closed trail, i.e., the beginning and ending vertices being the same and no edge is repeated, i.e., $e_j \neq e_k$ for $j \neq k$ and $v_{n+1} = v_1$ in $(\star)$, is termed as a tour or a circuit.

An Eulerian trail is a trail passing through all the edges in the graph.

An Eulerian tour is a tour passing through all the edges in the graph.

Eulerian tour theorem: Let $G$ be a connected undirected graph, then the following two statements are equivalent:

1. $G$ has an Eulerian tour.
2. All the vertices in $G$ are even.

If the graph has loops, i.e., an edge connecting the same vertex the above still holds true, provided we interpret that every loop counts to the degree of the vertex twice.

Proof: We will prove it for graphs without loops since the loops do not make any difference.

$1 \implies 2$. Since $G$ has an Eulerian tour, every time we enter a vertex we need to exit it. Further, the tour doesn't repeat an edge. Hence, every vertex has even degree.

$2 \implies 1$. This proceed by induction on the number of edges. The base case is when the number of edges is $2$. This corresponds to a graph with $2$ vertices and $2$ edges between these two vertices. Clearly, this has an Eulerian tour. Assume that all graphs with number of edges less than $m$ and with each vertex having even degree has an Eulerian tour. Now we will show that a graph with $m$ number of edges and with each vertex having even degree has an Eulerian tour. Pick any vertex. There exists a tour starting and ending at this vertex. To see this, if this were not to be possible, then we would end at a vertex from which we cannot escape. However, this can never happen since each vertex has even degree. Hence, we can pick a tour starting and ending at the same vertex. Let this tour be $T$ and be of length $n$ and say $v_1 e_1 v_2 e_2 \ldots v_{n-1} e_{n-1} v_n e_n v_1$. Once we have this we are done. Now remove these edges from the graph. We will then have at most $n$ connected components, say $C_1, C_2, \ldots, C_k$, where $k \leq n$. Now by induction hypothesis, there is a Eulerian tour on each of these connected components. Now we will obtain the Eulerian tour on the entire graph $G$. Now lets get back to the tour $T$ and start at $v_1$. Find the first time this tour intersects one of the connected components. Once it hits the connected component, complete the tour within this connected component and return to the place where the tour hit this connected component. Repeat this till we have visited all the connected components and finally complete the tour. Note that adding loops play no role since if we were to have loop(s) at a vertex, whenever we hit that vertex finish of the loop(s) and continue.

Handshaking lemma

The Handshaking lemma states that any finite undirected graph has an even number of vertices with odd-degree. This follows immediately from a more fundamental result, namely, the degree sum formula.

Degree sum formula: Given an undirected graph $G$, with the set of vertices $V$ and edges $E$, we have$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$ If the graph has loops, i.e., an edge connecting the same vertex the above still holds true, provided we interpret that every loop counts to the degree of the vertex twice. (Sometimes, degree sum formula is also called the handshaking lemma)

Proof: We will prove the result when the graph has no loops. Once we prove it for graphs with no loops, the result is evident for graphs with loops since every time we add a loop, the degree of a vertex increases by $2$ and so does the right hand side.

Let $\mathbb{I}(v_i,v_j)$ be the indicator function that denotes if there is an edge between the vertices $v_i$ and $v_j$. We then have
$$\sum_{v_i \in V;v_j \in V} \mathbb{I}(v_i,v_j) = 2 \vert E \vert \tag{$\star$}$$This is because each edge is incident to two vertices and hence each edge is counted twice in the above summation. However, $(\star)$ can also be rewritten as $$\sum_{v_i \in V} \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j)\right) = 2 \vert E \vert$$Now note that $\displaystyle \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j) \right)$ is nothing but the degree of the vertex $v_i$, since each time a vertex is adjacent to the vertex $v_i$, the count increases by $1$. Hence, we have what we want, i.e.,$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$This immediately implies that there has to be an even number of vertices with odd-degree. Let $V_e$ be the set of vertices with even degree and $V_o$ be the set of vertices with odd degree. We then have that$$\sum_{v \in V_e} \text{deg}(v) + \sum_{v \in V_o} \text{deg}(v) = 2\vert E \vert \tag{$\dagger$}$$Since every vertex in $V_e$ has an even degree, we have $\sum_{v \in V_e} \text{deg}(v)$ to be an even number. This and $(\dagger)$ implies $\sum_{v \in V_o} \text{deg}(v) \,\,\, (\perp)$ has to be even. Now each of $\deg(v)$ in $(\perp)$ is odd. If $\vert V_o \vert$ were to be odd, then $\sum_{v \in V_o} \text{deg}(v)$ will be odd (since an odd number of odd integers when added up will give an odd number), contradicting the fact that it has to be even.