
Section9.4Traversals: Eulerian and Hamiltonian Graphs

The subject of graph traversals has a long history. In fact, the solution by Leonhard Euler (Switzerland, 1707-83) of the Koenigsberg Bridge Problem is considered by many to represent the birth of graph theory.

Subsection9.4.1Eulerian Graphs

A map of the Prussian city of Koenigsberg (circa 1735) in Figure 9.4.1 shows that there were seven bridges connecting the four land masses that made up the city. The legend of this problem states that the citizens of Koenigsberg searched in vain for a walking tour that passed over each bridge exactly once. No one could design such a tour and the search was abruptly abandoned with the publication of Euler's Theorem.

The map of Koenigsberg can be represented as an undirected multigraph, as in Figure 9.4.2. The four land masses are the vertices and each edge represents a bridge.

The desired tour is then a path that uses each edge once and only once. Since the path can start and end at two different vertices, there are two remaining vertices that must be intermediate vertices in the path. If $x$ is an intermediate vertex, then every time that you visit $x\text{,}$ you must use two of its incident edges, one to enter and one to exit. Therefore, there must be an even number of edges connecting $x$ to the other vertices. Since every vertex in the Koenigsberg graph has an odd number of edges, no tour of the type that is desired is possible.

As is typical of most mathematicians, Euler wasn't satisfied with solving only the Koenigsberg problem. His original theorem, which is paraphrased below, concerned the existence of paths and circuits like those sought in Koenigsberg. These paths and circuits have become associated with Euler's name.

Definition9.4.4Eulerian Paths, Circuits, Graphs

A Eulerian path through a graph is a path whose edge list contains each edge of the graph exactly once. If the path is a circuit, then it is called a Eulerian circuit. A Eulerian graph is a graph that possesses a Eulerian circuit.

Without tracing any paths, we can be sure that the graph below has an Eulerian circuit because all vertices have an even degree. This follows from the following theorem.

It can be proven by induction that the number of vertices in an undirected graph that have an odd degree must be even. We will leave the proof of this fact to the reader as an exercise. The necessity of having either zero or two vertices of odd degree is clear from the proof of the Koenigsberg case of this theorem. Therefore, we will concentrate on proving that this condition is sufficient to ensure that a graph has an Eulerian path. Let $k$ be the number of vertices with odd degree.

Phase 1. If $k = 0$, start at any vertex, $v_0$, and travel along any path, not using any edge twice. Since each vertex has an even degree, this path can always be continued past each vertex that you reach except $v_0$. The result is a circuit that includes $v_0$. If $k =2$, let $v_0$ be either one of the vertices of odd degree. Trace any path starting at $v_0$ using up edges until you can go no further, as in the $k = 0$ case. This time, the path that you obtain must end at the other vertex of odd degree that we will call $v_1$. At the end of Phase 1, we have an initial path that may or may not be Eulerian. If it is not Eulerian, Phase 2 can be repeated until all of the edges have been used. Since the number of unused edges is decreased in any use of Phase 2, a Eulerian path must be obtained in a finite number of steps.

Phase 2. As we enter this phase, we have constructed a path that uses a proper subset of the edges in our graph. We will refer to this path as the current path. Let $V$ be the vertices of our graph, $E$ the edges, and $E_u$ the edges that have been used in the current path. Consider the graph $G' = \left(V, E - E_u\right)$. Note that every vertex in $G'$ has an even degree. Select any edge, $e$, from $G'.$ Let $v_a$ and $v_b$ be the vertices that $e$ connects. Trace a new path starting at $v_a$ whose first edge is $e$. We can be sure that at least one vertex of the new path is also in the current path since $(V, E)$ is connected. Starting at $v_a$, there exists a path in $(V, E)$ to any vertex in the current path. At some point along this path, which we can consider the start of the new path, we will have intersected the current path. Since the degree of each vertex in $G'$ is even, any path that we start at $v_a$ can be continued until it is a circuit. Now, we simply augment the current path with this circuit. As we travel along the current path, the first time that we intersect the new path, we travel along it (see Figure 9.4.8). Once we complete the circuit that is the new path, we resume the traversal of the current path.

If the result of this phase is a Eulerian path, then we are finished; otherwise, repeat this phase.

The complete undirected graphs $K_{2n+1}$, $n = 1, 2, 3, \ldots$. .., are Eulerian. If $n \geq 1$, then $K_{2n}$ is not Eulerian.

Subsection9.4.2Hamiltonian Graphs

To search for a path that uses every vertex of a graph exactly once seems to be a natural next problem after you have considered Eulerian graphs.The Irish mathematician Sir William Rowan Hamilton (1805-65) is given credit for first defining such paths. He is also credited with discovering the quaternions, for which he was honored by the Irish government with a postage stamp in 2004.

Definition9.4.11Hamiltonian Path, Circuit, and Graphs

A Hamiltonian path through a graph is a path whose vertex list contains each vertex of the graph exactly once, except if the path is a circuit, in which case the initial vertex appears a second time as the terminal vertex. If the path is a circuit, then it is called a Hamiltonian circuit. A Hamiltonian graph is a graph that possesses a Hamiltonian circuit.

Figure 9.4.14 shows a graph that is Hamiltonian. In fact, it is the graph that Hamilton used as an example to pose the question of existence of Hamiltonian paths in 1859. In its original form, the puzzle that was posed to readers was called “Around the World.” The vertices were labeled with names of major cities of the world and the object was to complete a tour of these cities. The graph is also referred to as the dodecahedron graph, where vertices correspond with the corners of a dodecahedron and the edges are the edges of the solid that connect the corners.

Unfortunately, a simple condition doesn't exist that characterizes a Hamiltonian graph. An obvious necessary condition is that the graph be connected; however, there is a connected undirected graph with four vertices that is not Hamiltonian. Can you draw such a graph?

Note9.4.16What Is Possible and What Is Impossible?

The search for a Hamiltonian path in a graph is typical of many simple-sounding problems in graph theory that have proven to be very difficult to solve. Although there are simple algorithms for conducting the search, they are impractical for large problems because they take such a long time to complete as graph size increases. Currently, every algorithm to search for a Hamiltonian path in a graph takes a time that grows at a rate that is greater than any polynomial as a function of the number of vertices. Rates of this type are called “super-polynomial.” That is, if $T(n)$ is the time it takes to search a graph of $n$ vertices, and $p(n)$ is any polynomal, then $T(n) > p(n)$ for all but possibly a finite number of positive values for $n\text{.}$

It is an unproven but widely held belief that no faster algorithm exists to search for Hamiltonian paths in general graphs. To sum up, the problem of determining whether a graph is Hamiltonian is theoretically possible; however, for large graphs we consider it a practical impossibility. Many of the problems we will discuss in the next section, particularly the Traveling Salesman Problem, are thought to be impossible in the same sense.

Definition9.4.17The $n$-cube

Let $n \geq 1$, and let $B^n$ be the set of strings of 0's and 1's with length $n$. The $n$-cube is the undirected graph with a vertex for each string in $B^n$ and an edge connecting each pair of strings that differ in exactly one position. The $n$-cube is normally denoted $Q_n\text{.}$

The $n$-cube is among the graphs that are defined within the graphs package of SageMath and is created with the expression graphs.CubeGraph(n).

Note9.4.18The Gray Code

A Hamiltonian circuit of the $n$-cube can be described recursively. The circuit itself, called the Gray Code, is not the only Hamiltonian circuit of the $n$-cube, but it is the easiest to describe. The standard way to write the Gray Code is as a column of strings, where the last string is followed by the first string to complete the circuit.

Basis for the Gray Code ($n = 1$): The Gray Code for the 1-cube is $G_1=\left( \begin{array}{c} 0 \\ 1 \\ \end{array} \right)$. Note that the edge between 0 and 1 is used twice in this circuit. That doesn't violate any rules for Hamiltonian circuits, but can only happen if a graph has two vertices.

Recursive definition of the Gray Code: Given the Gray Code for the $n$-cube, $n > 1$, then $G_{n+1}$ is obtained by (1) listing $G_n$ with each string prefixed with 0, and then (2) reversing the list of strings in $G_n$ with each string prefixed with 1. Symbolically, the recursion can be expressed as follows, where $G_n^r$ is the reverse of list $G_n$. $G_{n+1}=\left( \begin{array}{c} 0 G_n \\ 1 G_n^r \\ \end{array} \right)$

The Gray Codes for the 2-cube and 3-cube are $G_2= \left( \begin{array}{c} 00 \\ 01 \\ 11 \\ 10 \\ \end{array} \right) \textrm{ and }G_3=\left( \begin{array}{c} 000 \\ 001 \\ 011 \\ 010 \\ 110 \\ 111 \\ 101 \\ 100 \\ \end{array} \right)$

One application of the Gray code was discussed in the Introduction to this book. Another application is in statistics. In a statistical analysis, there is often a variable that depends on several factors, but exactly which factors are significant may not be obvious. For each subset of factors, there would be certain quantities to be calculated. One such quantity is the multiple correlation coefficient for a subset. If the correlation coefficient for a given subset, $A\text{,}$ is known, then the value for any subset that is obtained by either deleting or adding an element to $A$ can be obtained quickly. To calculate the correlation coefficient for each set, we simply travel along $G_n$, where $n$ is the number of factors being studied. The first vertex will always be the string of 0's, which represents the empty set. For each vertex that you visit, the set that it corresponds to contains the $k^{\text{th}}$ factor if the $k^{\text{th}}$ character is a 1.

Subsection9.4.3Exercises for Section 9.4

1

Locate a map of New York City and draw a graph that represents its land masses, bridges and tunnels. Is there a Eulerian path through New York? You can do the same with any other city that has at least two land masses.

Using a recent road map, it appears that an Eulerian circuit exists in New York City, not including the small islands that belong to the city. Lowell, Massachusetts, is located at the confluence of the Merrimack and Concord rivers and has several canals flowing through it. No Eulerian path exists for Lowell.

2

Which of the drawings in Figure 9.4.20 can be drawn without removing your pencil from the paper and without drawing any line twice?

3

Write out the Gray Code for the 4-cube.

Gray Code for the 4-cube: $G_4=\left( \begin{array}{c} 0000 \\ 0001 \\ 0011 \\ 0010 \\ 0110 \\ 0111 \\ 0101 \\ 0100 \\ 1100 \\ 1101 \\ 1111 \\ 1110 \\ 1010 \\ 1011 \\ 1001 \\ 1000 \\ \end{array} \right)$

4

Find a Hamiltonian circuit for the dodecahedron graph in Figure 9.4.14.

5

The Euler Construction Company has been contracted to construct an extra bridge in Koenigsberg so that a Eulerian path through the town exists. Can this be done, and if so, where should the bridge be built?

Any bridge between two land masses will be sufficient. To get a Eulerian circuit, you must add a second bridge that connects the two land masses that were not connected by the first bridge.

6

Consider the graphs in Figure 9.4.21. Determine which of the graphs have an Eulerian path, and find an Eulerian path for the graphs that have one.

7

Formulate Euler's theorem for directed graphs.

Let $G=(V,E)$ be a directed graph. $G$ has a Eulerian circuit if and only if $G$ is connected and $indeg(v)= outdeg(v)$ for all $v \in V\text{.}$ There exists a Eulerian path from $v_1 \textrm{ to } v_2$ if and only if $G$ is connected, $indeg(v_1)=outdeg(v_1)-1$, $indeg(v_2)= outdeg(v_2)+1$, and for all other vertices in $V$ the indegree and outdegree are equal.

8

Prove that the number of vertices in an undirected graph with odd degree must be even.

Hint

Prove by induction on the number of edges.

9
1. Under what conditions will a round-robin tournament graph be Eulerian?

2. Prove that every round-robin tournament graph is Hamiltonian.

For what values of $n$ is the $n$-cube Eulerian?