Section5.3Eulerian and Hamiltonian Graphs¶ permalink

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.

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

1. $x_0=x_t\text{;}$
2. for every $i=0,1,\dots t-1\text{,}$ $x_ix_{i+1}$ is an edge of $\bfG\text{;}$
3. for every edge $e\in E\text{,}$ there is a unique integer $i$ with $0\le i\lt t$ for which $e=x_ix_{i+1}\text{.}$

When $\bfG$ is eulerian, a sequence satisfying these three conditions is called an eulerian circuit. A sequence of vertices $(x_0,x_1,\dots,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 $\bfG$ that is eulerian. The output that will be produced is a list of the degrees of the vertices of the graph $\bfG$ followed by a drawing of $\bfG\text{.}$

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 $\bfH$ that is not eulerian. Again, the output is the list of degrees of $\bfH$ followed by a drawing of $\bfH\text{.}$

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.

Proof

As an example, consider the graph $\bfG$ 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\text{.}$

\begin{align*} C \amp =(1)\\ \amp =(1,2,4,3,1)\quad \text{start next from }2\\ \amp =(1,2,5,8,2,4,3,1)\quad\text{start next from } 4\\ \amp =(1,2,5,8,2,4,6,7,4,9,6,10,4,3,1)\quad\text{start next from } 7\\ \amp =(1,2,5,8,2,4,6,7,9,11,7,4,9,6,10,4,3,1)\quad\text{Done!!} \end{align*}

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.)

A graph $\GVE$ is said to be hamiltonian if there exists a sequence $(x_1,x_2,\dots,x_n)$ so that

1. every vertex of $\bfG$ appears exactly once in the sequence;
2. $x_1x_n$ is an edge of $\bfG\text{;}$ and
3. for each $i=1,2,\dots,n-1\text{,}$ $x_ix_{i+1}$ is an edge in $\bfG\text{.}$

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.

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

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.