Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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 Koenigsberg
(a)A map of Koenigsberg, circa 1735
(b)A multigraph for the bridges of Koenigsberg
Figure9.4.1The Koenigsberg Bridge Problem

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.

Proof

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.3Eulerian 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 path.

Example9.4.4An Eulerian Graph

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.

An Eulerian graph
Figure9.4.5An Eulerian graph
Proof
Example9.4.8Complete Eulerian Graphs

The complete undirected graphs \(K_2\) and \(K_{2n+1}\), \(n = 1, 2, 3, \ldots\). .., are Eulerian. If \(n>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.

Irish stamp honoring Sir William Rowan Hamilton
Figure9.4.9Irish stamp honoring Sir William Rowan Hamilton
Definition9.4.10Hamiltonian 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 path.

Example9.4.11The Original Hamiltonian Graph

Figure 9.4.13 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.

A Dodecahedron
The Dodecahedron Graph
Figure9.4.12A Dodecahedron
Figure9.4.13The Dodecahedron Graph
Problem9.4.14

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.15What 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.16The \(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 Sage and is created with the expression graphs.CubeGraph(n).

Note9.4.17The 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)\]

Example9.4.18Applications of the Gray Code

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.

Answer
2

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

Drawings for exercise 9-4-2
3

Write out the Gray Code for the 4-cube.

Answer
4

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

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?

Answer
6

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

graphs for exercise 9-4-6
Figure9.4.19Graphs for exercise 6
7

Formulate Euler's theorem for directed graphs.

Answer
8

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

Hint
9

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

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

Answer
10

For what values of \(n\) is the \(n\)-cube Eulerian?