3 Eulerian and Hamiltonian cycles 3 Eulerian and Hamiltonian cycles 3.2 Hamiltonian cycles

3.1 Euler’s theorem and König’s theorem on bi-partite graphs

Definition 3.1 (Eulerian graph).

A circuit in a graph visiting every edge exactly once and every vertex is called an Eulerian circuit and a graph that has an Eulerian circuit is called an Eulerian graph.

Exercise(A) 3.2.

Show that a finite graph is Eulerian iff $G$ is connected and is a edge-disjoint union of cycles i.e., $G=C_{1}\cup\cdots\cup C_{m}$ where $C_{i}$ ’s are cycles and have no common edges.

Theorem 3.3 (Euler’s theorem ; Veblen 1912.).

A finite connected graph is Eulerian iff every vertex has even degree.

First proof..

Since the graph is Eulerian, let $C_{1},\ldots,C_{m}$ be the partition into edge-disjoint cycles. Viewing $C_{i}$ ’s as graphs by themselves, observe that $d_{v}(C_{i})=21[v\in C_{i}]$ i.e., vertices in $C_{i}$ have degree $2$ and $0$ otherwise. Further, we have by edge-disjointness of $C_{i}$ ’s that

d_{v}(G)=\sum_{i}d_{v}(C_{i})=2\sum_{i}1[v\in C_{i}],

and thus proving that every vertex has even degree.

To show the converse, assume that the vertex degrees are all even. Let $x_{0}x_{1}\ldots x_{l}$ be a simple path of maximal length $l$ i.e., there is no simple path of length $>l$ . Since $d_{x_{0}}\geq 2$ , there exists a $y\in N(x_{0})\setminus\{x_{1}\}$ . Then $yx_{0}x_{1}\ldots x_{l}$ is a simple path of length $l+1$ and this yields a contradiction unless $y=x_{i}$ for some $1\leq i\leq l$ . Let $x_{i}=y$ . Then $x_{0}x_{1}\ldots x_{i}x_{0}$ is a cycle, say $C_{1}$ . Remove $C_{1}$ from $G$ and consider $G-C_{1}$ . All vertex degrees in $G-C_{1}$ are even. So, we can repeat the procedure for a component of $G-C_{1}$ with at least two vertices and obtain a cycle $C_{2}$ . Continuing this way, we obtain cycles $C_{3},\ldots C_{m}$ such that $G$ is a disjoint union of $C_{1},\ldots,C_{m}$ and hence $G$ is Eulerian by the claim above. ∎

Second proof..

The starting point for the proof is that every maximal trail in an even graph is closed (see Lemma below). Assume G has an Eulerian Tour, let it be C= $vv_{1}\cdots v_{k}v$ Consider $u\neq v\in V$ ,
Let u be visited m times in C. Note that in each visit two edges incident on u are being used. Hence, $\exists 2m$ edges incident on $u$ . Since, C is eulerian, there are no more edges on u. This shows that degree of u is even. On the other hand, assume v occurs $n$ times in C,

\therefore deg(v)=2(m-2)+2=2m-2

Hence, G is an even graph.
Conversely, Let G be an even connected graph with T= $v_{0}v_{1}v_{2}\cdots v_{l}$ being the maximal trail. By lemma given below, T is closed,i.e., $v_{0}-v_{l}$ . Assume, T is not Eulerian, then $\exists w\in V$ and $w\sim v_{i}$ for some $i$ with $(w,v_{i})\not\in$ T. Define, T’= $wv_{i}\cdots v_{l}\cdots v_{i}$ . This makes T’ longer than T leading to contradiction as T is maximal. Hence, T is Eulerian. ∎

Lemma 3.4.

Every maximal trail in an even graph (i.e., graph with even vertices) is closed.

Proof.

Let T be a maximal trail. Assume T is not closed. Let, T= $vv_{1}v_{2}\cdots v_{k}$
Now, the last entry is to $v_{k}$ and hence there is no exit. Also, $v_{k}\neq v$ . Hence, $v_{k}$ has odd number of edges in T. deg( $v$ ) is even and since edges are not repeated,
$\exists w\sim v$ such that $(v,w)$ is not visited by T. This shows that T+ $w$ is a trail which is larger than T. Hence, contradiction shows that our assumption was wrong, i.e., T is closed ∎

Exercise(A) 3.5 (Konigsberg problem).

Prove Euler’s theorem for multi-graphs and hence show that Konigsberg problem has no solution.

Sometimes usage of multi-graphs can simplify proofs of theorems for graphs.

Corollary 3.6.

Let $G$ be a connected graph. $G$ has an Eulerian trail iff there are $0$ or exactly $2$ vertices of odd degree.

Proof.

We have already proved that a finite connected graph $G$ has an eulerian circuit( which is just a closed eulerian trail) if and only if it has zero vertices of even degree.

Now we prove that a finite connected graph has an open eulerian trail if and only if it has exactly two vertices of odd degree.

Assume $G$ has an open Euler trail, $P$ . Suppose the trail begins at $v$ and ends at $w$ . Except for the first listing of $v$ and the last listing of $w$ every time a vertex is listed, that accounts for two edges adjacent to that vertex, the one before it in the list and the one after it in the list. This circuit uses every edge exactly once. So every edge is accounted for and there are no repeats. Thus every degree must be even, except for $v$ and $w$ which must be odd.

Now suppose $v$ and $w$ are the vertices of odd degree. Consider $G+e$ where $e$ is a new edge between $v$ and $w$ . This graph has all even degrees. Thus it has an eulerian circuit. This circuit travels through edge $e$ too. On removing edge $e$ we get an euler trail in $G$ .

∎

Can you prove the above corollary without appealing to multi-graphs ?

Exercise(A) 3.7.

Every closed odd length walk contains an odd length cycle.

Theorem 3.8 (König’s theorem).

A graph is bi-partite iff it has no odd cycles.

The König here is the hungarian mathematician Dénes König whose father Gyola König was also a well-known mathematician. Dénes wrote the first book on graph theory.

Proof.

The only if part : Suppose $G$ is bi-partite with partition $V=V_{1}\sqcup V_{2}$ . Let $v_{0}v_{1}\ldots,v_{k}v_{0}$ be a cycle. WLOG¹¹ 1 Without loss of generality, suppose $v_{o}\in V_{1}$ . By bi-partiteness, $v_{i}\in V_{2}$ for $1\leq i\leq k$ and $i$ odd and $v_{i}\in V_{1}$ for $1\leq i\leq k$ and $i$ even. Since $v_{k}\sim v_{0}$ , $v_{k}\in V_{2}$ and hence $k$ is odd. Thus, the length of the cycle $k+1$ is even.

The if part : Let $v_{0}\in V$ . Set $v\in V_{1}$ if $d_{G}(v_{0},v)$ is even and else $v\in V_{2}$ . WLOG, suppose $v\sim w$ for $v,w\in V_{1}$ . Then Let $P,P^{\prime}$ be respectively the shortest paths from $v_{0}$ to $v, w$ respectively. Let $P*$ be the inversed path from $v$ to $v_{0}$ . Since $v,w\in V_{1}$ , $P*,P^{\prime}$ have even lengths and so $P^{\prime}wvP*$ is a closed walk starting at $v$ and has odd length. By Lemma(3.7), it has an odd length cycle, a contradiction. Thus there are no edges between vertices in $V_{1}$ or $V_{2}$ respectively i.e., $G$ is bi-partite with partition $V_{1}\sqcup V_{2}$ . ∎