5.3: Eulerian and Hamiltonian Graphs

Graph theory is an area of mathematics that has found many applications in a variety of disciplines. Throughout this text, we will encounter a number of them. However, graph theory traces its origins to a problem in Königsberg, Prussia (now Kaliningrad, Russia) nearly three centuries ago. The river Pregel passes through the city, and there are two large islands in the middle of the channel. These islands were connected to the mainland by seven bridges as indicated in Figure 5.12. It is said that the citizens of Königsberg often wondered if it was possible for one to leave his home, walk through the city in such a way that he crossed each bridge precisely one time, and end up at home again. Leonhard Euler settled this problem in 1736 by using graph theory in the form of Theorem 5.13.

Figure 5.12. The bridges of Königsberg

Let \(\textbf{G}\) be a graph without isolated vertices. We say that \(\textbf{G}\) is eulerian provided that there is a sequence \((x_0,x_1,x_2,…,x_t)\) of vertices from \(\textbf{G}\), with repetition allowed, so that

1. \(x_0 = x_t\);
2. for every \(i = 0,1,...,t-1\), \(x_ix_{i+1}\) is an edge of \(\textbf{G}\);
3. for every edge \(e \in E\), there is a unique integer \(i\) with \(0 \leq i < t\) for which \(e = x_ix_{i+1}\).

When \(\textbf{G}\) is eulerian, a sequence satisfying these three conditions is called an eulerian circuit. A sequence of vertices \((x_0,x_1,…,x_t)\) is called a circuit when it satisfies only the first two of these conditions. Note that a sequence consisting of a single vertex is a circuit. Before proceeding to Euler's elegant characterization of eulerian graphs, let's use SageMath to generate some graphs that are and are not eulerian.

Run the code below. It will execute until it finds a graph \(\textbf{G}\) that is eulerian. The output that will be produced is a list of the degrees of the vertices of the graph \(\textbf{G}\) followed by a drawing of \(\textbf{G}\).

// code 1

We encourage you to evaluate the run the code above multiple times, even changing the number of vertices and edges. If it seems to be running a log time, it may be that you have made the number of edges too small, so try increasing it a bit. Do you notice anything about the degrees of the vertices in the graphs produced?

Now let's try to find a graph \(\textbf{H}\) that is not eulerian. Again, the output is the list of degrees of \(\textbf{H}\) followed by a drawing of \(\textbf{H}\).

// code 2

One thing you probably noticed in running this second block of code is that it tended to come back much faster than the first. That would suggest that the non-eulerian graphs outnumber the eulerian graphs. Did you notice anything different about the degrees of the vertices in these graphs compared to the ones that were eulerian?

The following elementary theorem completely characterizes eulerian graphs. Its proof gives an algorithm that is easily implemented.

Theorem 5.13

A graph \(\textbf{G}\) is eulerian if and only if it is connected and every vertex has even degree.

Proof

Clearly, an eulerian graph must be connected. Also, if \((x_0,x_1,…,x_t)\) is an eulerian circuit in \(\textbf{G}\), then for each \(i=0,1,…,t−1\), we can view the edge \(x_ix_{i+1}\) as exiting \(x_i\) and entering \(x_{i+1}\). The degree of every vertex must be even, since for each vertex \(x\), the number of edges exiting \(x\) equals the number of edges entering \(x\). Furthermore, each edge incident with \(x\) either exits from \(x\) or enters \(x\).

We now describe a deterministic process that will either (a) find an eulerian circuit, (b) show that the graph is disconnected, or (c) find a vertex of odd degree. The description is simplified by assuming that the vertices in \(\textbf{G}\) have been labelled with the positive integers \(1,2,…,n\), where \(n\) is the number of vertices in \(\textbf{G}\). Furthermore, we take \(x_0=1\).

We launch our algorithm with a trivial circuit \(C\) consisting of the vertex \(x_0=(1)\). Thereafter suppose that we have a partial circuit \(C\) defined by \((x_0,x_1,…,x_t)\) with \(x_0=x_t=1\). The edges of the form \(x_ix_{i+1}\) have been traversed, while the remaining edges in \(\textbf{G}\) (if any) have not. If the third condition for an euler circuit is satisfied, we are done, so we assume it does not hold.

We then choose the least integer \(i\) for which there is an edge incident with \(x_i\) that has not already been traversed. If there is no such integer, since there are edges that have not yet been traversed, then we have discovered that the graph is disconnected. So we may assume that the integer \(i\) exists. Set \(u_0=x_i\). We define a sequence \((u_0,u_1,…,u_s)\) recursively. If \(j \geq 0\), set

\(N_j = \{y: u_jy\) is an edge in G and has not yet been traversed.\(\}\)

If \(N_j \neq \0 \), we take \(u_{j+1}\) as the least positive integer in \(N_j\). If \(N_j = 0\), then \(j \geq 1\) and we take \(s=j\) and halt this subroutine. \

When the subroutine halts, we consider two cases. If \(u_0 \ neq u_s, then \(u_0\) and \(u_s\) are vertices of odd degree in \(\textbf{G}\). So we are left to consider the case where \(u_0 = u_s = x_i\). In this case, we simply expand our original sequence \((x_0,x_1,...,x_t)\) by replacing the integer \(x_i\) by the sequence \((u_0, u_1,...,u_s)\).

As an example, consider the graph \(\textbf{G}\) shown in Figure 5.14. Evidently, this graph is connected and all vertices have even degree. Here is the sequence of circuits starting with the trivial circuit \(C\) consisting only of the vertex 1.

\begin{alligned}

C &= (1) \

&= (1,2,4,3,1) \text{start next from 2} \

&=(1,2,5,8,2,4,3,1) \text{start next from 4} \

&=(1,2,5,8,2,4,6,7,4,9,6,10,4,3,1) \text{start next from 7} \

&=(1,2,5,8,2,4,6,7,9,11,7,4,9,6,10,4,3,1) \text{Done!!}

\end{alligned}

Figure 5.14. An Eulerian Graph

You should note that Theorem 5.13 holds for loopless graphs in which multiple edges are allowed. Euler used his theorem to show that the multigraph of Königsberg shown in Figure 5.15, in which each land mass is a vertex and each bridge is an edge, is not eulerian, and thus the citizens could not find the route they desired. (Note that in Figure 5.15 there are multiple edges between the same pair of vertices.)

Figure 5.15 The multigraph of Königsberg's bridges

A graph \(\textbf{G} = (V,E)\) is said to be hamiltonian if there exists a sequence \((x_1,x_2,…,x_n)\) so that

1. every vertex of \(\textbf{G}\) appears exactly once in the sequence
2. \(x_1x_n\) is an edge of \(\textbf{G}\)
3. for each \(i = 1,2,...,n-1,x_ix_{i+1}\) is an edge in \(\textbf{G}\).

Such a sequence of vertices is called a hamiltonian cycle.

The first graph shown in Figure 5.16 both eulerian and hamiltonian. The second is hamiltonian but not eulerian.

Figure 5.16. Eulerian and Hamiltonian Graphs

In Figure 5.17, we show a famous graph known as the Petersen graph. It is not hamiltonian.

Figure 5.17. The Petersen Graph

Unlike the situation with eulerian circuits, there is no known method for quickly determining whether a graph is hamiltonian. However, there are a number of interesting conditions which are sufficient. Here is one quite well known example, due to Dirac.

Theorem 5.18

If \(\textbf{G}\) is a graph on \(n\) vertices and each vertex in \(\textbf{G}\) has at least \(⌈\frac{n}{2}⌉\) neighbors, then \(\textbf{G}\) is hamiltonian.

Proof

Suppose the theorem fails and let \(n\) be the least positive integer for which there exists a graph \(\textbf{G}\) on \(n\) vertices so that each vertex in \(\textbf{G}\) has at least \(⌈n/2⌉\) neighbors, yet there is no hamiltonian cycle in \(\textbf{G}\). Clearly, \(n \geq 4\).

Now let \(t\) be the largest integer for which \(\textbf{G}\) has a path \(P=(x_1,x_2,…,x_t)\) on \(t\) vertices. Clearly all neighbors of both \(x_1\) and \(x_t\) appear on this path. By the pigeon hole principle, there is some integer \(i\) with \(1 \leq i < t\) so that \(x_1x_{i+1}\) and \(x_ix_t\) are edges in \(\textbf{G}\). However, this implies that

\(C = (x_1,x_2,x_3,...,x_i,x_t,x_{t-1},x_{t-2},...,x_{i+1})\)

is a cycle of length \(t\) in \(\textbf{G}\). In turn, this requires \(⌈n/2⌉<t<n\). But if \(y\) is any vertex not on the cycle, then \(y\) must have a neighbor on \(C\), which implies that \(\textbf{G}\) has a path on \(t+1\) vertices. The contradiction completes the proof.