12.8: Hamilton Cycles

Last updated
Save as PDF

Page ID: 129675

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Figure 12.177 The symmetries of an icosahedron, with 30 edges, 20 faces, and 12 vertices, can be analyzed using graph theory. (credit: "Really big icosahedron" by Clayton Shonkwiler/Wikimedia, CC BY 2.0)

Learning Objectives

After completing this section, you should be able to:

Describe and identify Hamilton cycles.
Compute the number of Hamilton cycles in a complete graph.
Apply and evaluate weighted graphs.

In Euler Circuits and Euler Trails, we looked for circuits and paths that visited each edge of a graph exactly once. In this section, we will look for circuits that visit each vertex exactly once. Like many concepts in graph theory, the idea of a circuit that visits each vertex once was inspired by games and puzzles. As early as the 9th century, Indian and Islamic intellectuals wondered whether it was possible for a knight to visit every space on a chess board of a given size, which is equivalent to visiting every vertex of a graph that represents the chess board.

In 1857, a mathematician named William Rowan Hamilton invented a puzzle in which players were asked to find a route along the edges of a dodecahedron (see Figure 12.178), which visited every vertex exactly once. Let’s explore how graph theory provides insight into these games as well as practical applications such as the Traveling Salesperson Problem.

Figure 12.178 A Dodecahedron

Hamilton’s Puzzle

Before we look at the solution to Hamilton's puzzle, let’s review some vocabulary we used in Figure 12.179. It will be helpful to remember that directed cycle is a type of circuit that doesn’t repeat any edges or vertices.

Three concentric ovals represent directed cycles, circuits, and closed walks. The first (inner) oval labeled directed cycles (closed paths) reads, no repeated edges or vertices. The second oval labeled circuits (closed talks) reads, no repeated edges. The third oval is labeled closed walks.

Figure 12.179 Closed Walks, Circuits, and Directed Cycles

The goal of Hamilton's puzzle was to find a route along the edges of the dodecahedron, which visits each vertex exactly once. A dodecahedron is a three-dimensional space figure with faces that are all pentagons as we saw in Figure 12.178.

Since it is easier to visualize two dimensions rather than three, we will flatten out the dodecahedron and look at the edges and vertices on a flat surface. Graph A in Figure 12.180 shows a two-dimensional graph of the edges and vertices, and Graph B shows an untangled version of Graph A in which no edges are crossing. Graph B in Figure 12.180 is very similar to the design of the game board that Hamilton invented for his puzzle.

Two graphs are labeled graph A and graph B. Graph A highlights the edges of a dodecahedron. Graph B highlights the vertices of a dodecahedron.

Two figures. The first figure is a 2 D view of a dodecahedron. The edges are highlighted. The second figure is a 3 D view of a dodecahedron. The edges in the front face are highlighted.

Figure 12.180 Graph of Edges and Vertices of Dodecahedron

We can see that this is a planar graph because it can be “untangled.” In order to solve Hamilton’s puzzle, we need to find a circuit that visits every vertex once. A solution is shown in Figure 12.181.

A 2 D view of a dodecahedron. The edges are highlighted.

Figure 12.181 A Solution to Hamilton’s Puzzle

A circuit that doesn’t repeat any vertices, like the one in Figure 12.181, is called a directed cycle. So, we can most accurately say that Hamilton’s puzzle asks us to find a directed cycle that visits every vertex in a graph exactly once. Because Hamilton created and solved this puzzle, these special circuits were named Hamilton cycles, or Hamilton circuits.

Who Knew?

Icosian Game

When Hamilton invented his puzzle in the 19th century, it was originally called the Icosian game. This was a reference to an icosahedron, not a dodecahedron. Why? Hamilton was actually interested in the symmetries of icosahedrons. It turns out that these two space figures are related to each other. The dodecahedron has 30 edges, 20 faces, and 12 vertices, while the icosahedron has 30 edges, 12 faces, and 20 vertices. By relating the vertices of the dodecahedron to the faces of the icosahedron, Hamilton was able to make the mathematical connections necessary to use graph theory and dodecahedrons to make discoveries about the symmetries of icosahedrons.

Hamilton Cycles vs. Euler Circuits

Let’s practice naming and identifying Hamilton cycles, as well as distinguishing them from Euler circuits. It is important to remember that Euler circuits visit all edges without repetition, while Hamilton cycles visit all vertices without repetition. Hamilton cycles are named by their vertices just like all circuits. An example is given in Figure 12.182.

Two graphs. The first graph, graph Z has four vertices: a, b, c, and d. The edges connect a b, b c, c d, d a, and a c. The second graph directed edges from a to b, b to c, c to d, and d to a. A dashed line connects a to c.

Figure 12.182 Hamilton Cycle in Graph Z

Notice that the Hamilton cycle a → b → c → d for Graph Z in Figure 12.182 is NOT an Euler circuit, because it does not visit edge $ac$ . Some Hamilton cycles are also Euler circuits while some are not, and some Euler circuits are Hamilton cycles while some are not.

Checkpoint

TIP! Sometimes students confuse Euler circuits with Hamilton cycles. To help you remember, think of the E in Euler as standing for Edge.

Example 12.33

Differentiating between Hamilton Cycles or Euler Circuits

Use Figure 12.183 to determine whether the given circuit is a Hamilton cycle, an Euler circuit, both, or neither.

Graph Q has two overlapping quadrilaterals. The vertices of the outer quadrilateral are a, c, h, and f. The vertices of the inner quadrilateral are d, b, e, and g. The vertex, d rests on the edge a f. The vertex, b rests on the edge a c. The vertex, e rests on the edge c h. The vertex, g rests on the edge hf.

Figure 12.183 Graph Q

a → b → c → e → h → g → f → d → a
g → e → h → g → f → d → a → b → d → g
a → b → c → e → h → g → f → d → b → e → g → d → a

Answer

This circuit is a Hamilton cycle only. It visits each vertex exactly once, so, it is a Hamilton cycle. It is not an Euler circuit because it doesn’t visit all of the edges.
This circuit is neither Hamilton cycle nor an Euler circuit. It doesn’t visit vertex $c$ , so, it is not a Hamilton cycle. It also doesn’t visit edges $be$ and $ce$ , so, it is not an Euler circuit.
This circuit is an Euler circuit only. It visits several vertices more than once; so, it is not a Hamilton cycle. It visits every edge exactly once, so, it is an Euler circuit.

Checkpoint

TIP! Euler circuits never skip a vertex, so, they only fail to be Hamilton cycles when they visit a vertex more than once. Hamilton cycles never visit any edges twice, so, they only fail to be Euler circuits when they skip edges.

Your Turn 12.33

Consider the figure shown. Is the circuit a → b → f → e → h → i → g → d → c → a an Euler circuit, a Hamilton cycle, or both?

Graph T has 9 vertices. The edges connect a b, b f, f e, e h, h i, I g, g d, d c, and c a.

Figure 12.184 Graph T

Notice that the graph is a cycle. A cycle will always be Eulerian because all vertices are degree 2. Moreover, any circuit in the graph will always be both an Euler circuit and a Hamilton cycle. It is not always as easy to determine if a graph has a Hamilton cycle as it is to see that it has an Euler circuit, but there is a large group of graphs that we know will always have Hamilton cycles, the complete graphs. Since all vertices in a complete graph are adjacent, we can always find a directed cycle that visits all the vertices. For example, look at the directed six-cycle, n → o → p → q → r → s, in the complete graph with six vertices in Figure 12.185.

A directed graph has six vertices: o, p, q, r, s, and n. All the vertices are interconnected. Directed arrows flow from o to p, p to q, q to r, r to s, s to n, and n to o.

Figure 12.185 Directed Cycle in Complete Graph

That is not the only directed six-cycle in the graph though. We could find another just be reversing the direction, and we could find even more by using different edges. So, how many Hamilton cycles are in a complete graph with $n$ vertices? Before we tackle this problem, let’s look at a shorthand notation that we use in mathematics which will be helpful to us.

Factorials

In many areas of mathematics, we must calculate products like $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ or $11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ , products that involve multiplying all the counting numbers from a particular number down to 1. Imagine that the product happened to be all the numbers from 100 down to 1. That’s a lot of writing! Instead of writing all of that out, mathematicians came up with a shorthand notation. For example, instead of $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ , we write $7!$ , which is read “7 factorial.” In other words, the product of all the counting numbers from $n$ down to 1 is called $n$ factorial and it is written $n!$

Example 12.34

Evaluating Factorials

Evaluate $n!$ and $(n - 1)!$ for $n = 4$ .

Answer

$n! = 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ and $(n - 1)! = (4 - 1)! = 3! = 3 \cdot 2 \cdot 1 = 6$

Your Turn 12.34

Evaluate /**/n!/**/ and /**/(n - 1)!/**/ for /**/n = 6/**/.

A common use for factorials is counting the number of ways to arrange objects. Suppose that there were three students, Aryana, Byron, and Carlos, who wanted to line up in a row. How many arrangements are possible? There are six possibilities: ABC, ACB, BAC, BCA, CAB, or CBA. Notice that there were three students being arranged, and the number of possible arrangements is three.

FORMULA

The number of ways to arrange $n$ distinct objects is $n!$ .

Example 12.35

Counting Arrangements of Letters

Find the number of ways to arrange the letters a, b, c, and d.

Answer

$4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

Your Turn 12.35

Find the number of ways to arrange the letters v, w, x, y, and z.

Counting Hamilton Cycles in Complete Graphs

Now, let’s get back to answering the question of how many Hamilton cycles are in a complete graph. In Table 12.8, we have drawn all the four cycles in a complete graph with four vertices. Remember, cycles can be named starting with any vertex in the cycle, but we will name them starting with vertex $a$ .

Complete Graph	Cycle	Cycle	Cycle

A graph with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines.

A graph with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a d, and b c are in dashed lines.

A graph with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and d c are in dashed lines.

Cycle Name Clockwise (a, b, c, d) (a, b, d, c) (a, c, b, d) Cycle Name Counterclockwise (a, d, c, b) (a, c, d, b) (a, d, b, c)

Table 12.8 Four-Cycles in Complete Graph with Four Vertices

Table 12.8 shows that there are three unique four-cycles in a complete graph with four vertices. Notice that there were two ways to name each cycle, one reading the vertices in a clockwise direction and one reading the vertices in a counterclockwise direction. This is important to us because we are interested in Hamilton cycles, which are directed cycles. Although the cycles (a, b, c, d) and (a, d, c, b) are the same cycle, the directed cycles, a → b → c → d → a and a → d → c → b → a, which travel the same route in reverse order are considered different directed cycles, as shown in Table 12.9.

Complete Graph	Cycle	Cycle	Cycle

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines.

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a d, and b c are in dashed lines.

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and d c are in dashed lines.

Clockwise Hamilton Cycle

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a c, and b d are in dashed lines. Directed edges flow from a to d, d to c, c to b, and b to a.

a → b → c → d → a

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a d, and b c are in dashed lines. The directed edges flow from a to c, c to d, d to b, and b to a.

a → b → d → c → a

A grah with four vertices, a, b, c, and d. Edges connect a b, b c, c d, d a, a c, and b d. The edges, a b, and d c are in dashed lines. The edges flow from a to d, d to b, b to c, c, and c to a.

a → c → b → d → a

Counter-clockwise Hamilton Cycle

In this graph, four vertices, a, b, c, and d are present. Edges connect a b, b c, c d, d a, a c, and b d. In this eighth graph, the edges, a c, and b d are in dashed lines. Directed edges flow from a to d, d to c, c to b, and b to a.

a → d → c → b → a

In this graph, four vertices, a, b, c, and d are present. Edges connect a b, b c, c d, d a, a c, and b d. In this ninth graph, the edges, a d, and b c are in dashed lines. The directed edges flow from a to c, c to d, d to b, and b to a.

a → c → d → b → a

In this graph, four vertices, a, b, c, and d are present. Edges connect a b, b c, c d, d a, a c, and b d. In this tenth graph, the edges, a b, and d c are in dashed lines. The edges flow from a to d, d to b, b to c, c, and c to a.

a → d → b → c → a

Table 12.9 Hamilton Cycles in a Complete Graph with Four Vertices

The six directed four-cycles in Table 12.9 are the only distinct Hamilton cycles in a complete graph with four vertices. Six is also the number of ways to arrange the three letters b, c, and d. (Do you see why?) The number of ways to arrange three letters is $3! = 3 \cdot 2 \cdot 1 = 6$ . Similarly, the number of Hamilton cycles in a graph with five vertices is the number of ways to arrange four letters, which is $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ . In general, to find the number of Hamilton cycles in a graph, we take one less than the number of vertices and find its factorial.

FORMULA

The number of distinct Hamilton cycles in a complete graph with $n$ vertices is $(n - 1)!$

Example 12.36

Counting Hamilton Cycles in a Complete Graph

How many Hamilton cycles are in the complete graph in Figure 12.186?

Graph L has five vertices: m, n, o, p, and q. All vertices are interconnected.

Figure 12.186 Complete Graph L

Answer

There are five vertices in the graph. Using $n = 5$ , we have $(n - 1)! = (5 - 1)! = 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ Hamilton cycles.

Your Turn 12.36

How many Hamilton cycles are in the graph?

Graph R has six vertices: s, t, x, u, w, and v. All vertices are interconnected.

Figure 12.187 Complete Graph R

Weighted Graphs

Suppose that an officer in the U.S. Air Force who is stationed at Vandenberg Air Force base must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needs to visit each base once. The vertices in the graph in Figure 12.188 represent the four U.S. Air Force bases, Vandenberg, Edwards, Los Angeles, and Beale. The edges are labeled to with the driving distance between each pair of cities.

A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.

Figure 12.188 Graph of Four California Air Force Bases

The graph in Figure 12.188 is called a weighted graph, because each edge has been assigned a value or weight. The weights can represent quantities such as time, distance, money, or any quantity associated with the adjacent vertices joined by the edges. The total weight of any walk, trail, or path is the sum of the weights of the edges it visits.

Notice that the officer’s trip can be represented as a Hamilton cycle, because each of the four vertices in the graph is visited exactly once.

Example 12.37

Finding Hamilton Cycles of Lowest Weight

Use Figure 12.188 and the given Hamilton cycles to answer the following questions.

V → L → E → B → V

V → L → B → E → V

V → E → L → B → V

V → B → E → L → V

Which of the Hamilton cycles (directed cycles) lie on the same cycle (undirected cycle) in the graph?
Find the total weight of each cycle.
Of the four, which of the Hamilton cycles describes the shortest trip for the officer? Describe the route.

Answer

V → L → E → B → V and V → B → E → L → V follow the same edges in reverse order.
Any Hamilton cycles that lie on the same cycle will have the same edges and the same total weight.
V → L → E → B → V and V → B → E → L → V each have total weight $159 + 106 + 410 + 396 = 1071$ .

V → L → B → E → V has a total weight $159 + 439 + 410 + 207 = 1215$ .

V → E → L → B → V has a total weight $396 + 439 + 106 + 207 = 1148$ .
Hamilton cycles V → L → E → B → V and V → B → E → L → V each have the lowest total weight. The officer would take the route from Vandenberg, to Los Angeles, to Edwards, to Beale, and back to Vandenberg, or reverse that route.

Your Turn 12.37

Find the weight of the Hamilton cycle m → o → p → n → q → m in the given figure.

A graph with 5 vertices: m, n, o, p, and q. The edges from m to q, p, o, and n are labeled 5, 5, 3, and 4. The edges from n to q, p, and o are labeled 8, 5, and 6. The edges from p to o and q are labeled 5 and 7. The edge from q to o is labeled 2.

Figure 12.189 Weighted Complete Graph with Five Vertices

Check Your Understanding

For the following exercises, fill in the blank to make the statement true.

57.

A Hamilton cycle is a circuit that visits each ___________ exactly once.

58.

A __________ graph with /**/n \geq 3/**/ vertices has /**/\left( {n - 1} \right)!/**/ Hamilton cycles.

For the following exercises, fill in the blank with is or is not to make the statement true.

59.

A Hamilton cycle ________ a circuit.

60.

A Hamilton cycle that visits every edge ________ an Euler circuit.

61.

A Hamilton cycle ________ different from a Hamilton circuit.

62.

An Euler circuit that visits every vertex ________ a Hamilton cycle.

63.

The total weight of a trail _______ the sum of the weights of the edges visited by the trail.

64.

A weighted graph _______ always a complete graph.

65.

The number of ways to arrange n objects _______ /**/\left( {n - 1} \right)!/**/

66.

Every cycle ____ a circuit.

Section 12.7 Exercises

For the following exercises, use the figure to determine whether the sequence of vertices in the given graph is a Hamilton cycle, an Euler circuit, both, or neither.
$Three graphs. Graph A has six vertices: c, d, e, b, f, and g. Edges connect c d, d e, e g, d g, d f, b f, b g, c f, and f g. Graph L has six vertices: h, i, n, k, j, and m. Edges connect h i, i n, n k, i k, i j, k j, k m, m j, and j h. Graph U has seven vertices: t, s, r, o, q, v, and w. Edges connect to, t s, s r, r w, q o, q v, and w v.$

Graph A: f → b → g → e → d → c → f

Graph A: g → b → f → c → d → e → g

Graph A: d → e → g → d → f → b → g → f → c → d

Graph L: h → i → k → n → j → h

Graph L: n → i → h → j → m → k → n

Graph L: j → i → n → k → i → j → k → m → j

Graph U: v → w → r → s → t → o → q → v

Graph U: w → q → r → s → t → o → v → w

For the following exercises, use the figure to find a circuit that fits the description.
$Two graphs. Graph P has seven vertices labeled a to g. The edges connect a b, b e, a e, b c, b d, d f, e f, e d, d c, f c, c g, and f g. Graph Q has 7 vertices labeled h, i, j, k, n, m, and o. The edges connect h i, h k, k n, i n, i j, j n, n m, m i, j m, i k, j m, m o, and o k.$

A Hamilton cycle in Graph P that begins at vertex c.

10.

An Euler circuit in Graph P that begins at vertex c.

11.

A directed cycle in Graph P that is NOT a Hamilton cycle, and explain why it is not a Hamilton cycle.

12.

A directed circuit in Graph P that is NOT an Euler circuit, and explain why it is not an Euler circuit.

13.

A Hamilton cycle in Graph Q that begins at vertex n.

14.

An Euler circuit in Graph Q that begins at vertex n.

15.

A directed cycle in Graph Q that is NOT a Hamilton cycle, and explain why it is not a Hamilton cycle.

16.

A directed circuit in Graph Q that is NOT an Euler circuit, and explain why it is not an Euler circuit.

17.

Use the results of Exercises 9–16 to make an observation about which tends to involve a longer sequence of vertices, Hamilton cycles or Euler circuits. Explain why you think this is.

For the following exercises, evaluate the factorial expression for the given value of /**/n/**/.

18.

/**/n!,\,{n} = 10/**/

19.

/**/n!,\,{n} = 11/**/

20.

/**/\left( {n - 1} \right)!,\,{n} = 10/**/

21.

/**/\left( {n - 1} \right)!,\,{n} = 11/**/

For the following exercises, find the number of arrangements letters in the given word.

22.

have

23.

teamwork

24.

anime

25.

making

For the following exercises, find the number of Hamilton cycles in a complete graph with the given number of vertices.

26.

12 vertices

27.

13 vertices

28.

9 vertices

29.

8 vertices

30.

/**/x/**/ vertices

For the following exercises, given the number of Hamilton cycles in a complete graph, determine the number of vertices.

31.

/**/5! = 120/**/ Hamilton cycles

32.

/**/6! = 720/**/ Hamilton cycles

33.

/**/7! = 5040/**/ Hamilton cycles

34.

/**/x!/**/ Hamilton cycles

For the following exercises, all the distinct Hamilton cycles for a complete graph are given. Indicate which pairs of Hamilton cycles (directed cycles) lie on the same cycle (undirected cycle) in the graph.

35.

b → a → c → d → b
b → a → d → c → b
b → c → a → d → b
b → c → d → a → b
b → d → a → c → b
b → d → c → a → b

36.

i → f → g → h → e → i
i → f → g → e → h → i
i → f → h → g → e → i
i → f → h → e → g → i
i → f → e → g → h → i
i → f → e → h → g → i
i → g → f → h → e → i
i → g → f → e → h → i
i → g → h → f → e → i
i → g → h → e → f → i
i → g → e → f → h → i
i → g → e → h → f → i
i → h → g → f → e → i
i → h → g → e → f → i
i → h → f → g → e → i
i → h → f → e → g → i
i → h → e → g → f → i
i → h → e → f → g → i
i → e → g → h → f → i
i → e → g → f → h → i
i → e → h → g → f → i
i → e → h → f → g → i
i → e → f → g → h → i
i → e → f → h → g → i

For the following exercises, use the figure to find the weight of the given Hamilton cycle.
$Graph Z has nine vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows. 1, q to t. 2, s to v. 3, r to s. 4, q to u. 5, u to y. 6, r to v. 7, r to u. 8, v to y. 9, w to x. 10, x to y. 1, u to x. 12, t to w. 13, q to r. 14, t to u. 15, u to v.$

37.

q → r → s → v → y → x → w → t → u → q

38.

u → y → x → w → t → q → r → s → v → u

39.

y → v → s → r → u → q → t → w → x → y

40.

u → v → s → r → q → t → w → x → y → u

41.

The neighborhood of Pines West has three cul-de-sacs that meet at an intersection as shown. A postal delivery person starts at the intersection and visits each house in a cul-de-sac once, returns to the intersection, visits each house in the next cul-de-sac, and so on, returning to the intersection when finished. Describe how the route can be represented as a graph. If there is no backtracking, in other words, the person never reverses direction, is the route followed by the postal delivery person best described as a trail, an Euler circuit, a Hamilton cycle, or neither? Explain your reasoning.
$A map of Pines West. The map shows a start point at the center leading to three paths. Each path has six vertices. The start point is indicated by a vertex.$

42.

In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The 8 possible moves a knight can make from a given space are shown in the figure.
$An illustration shows a 5 by 5 square chess board. The knight is at the center of the board. The knight moves in an L-shape and it is indicated by 8 arrows. It moves either two steps left or right followed by one step up or down, or two steps up or down followed by one step left or right.$
A graph in which each vertex represents a space on a five-by-six game board and each edge represents a move a knight could make is shown in the figure.
$An illustration shows a 5 by 6 chessboard. Each square has a vertex. It displays several edges representing all possible knight moves. An illustration shows vertices arranged in 5 rows and 6 columns. The edges represent the knight's moves.$
A knight’s tour is a sequence of moves by a knight on a chessboard (of any size) such that the knight visits every square exactly once. If the knight’s tour brings the knight back to its starting position on the board, it is called a closed knight’s tour. Otherwise, it is called an open knight’s tour.
$A graph represents a knight's moves on a 5 by 6 chessboard. The knight is at the bottom-left square. The knight moves in an L-shape. The movement of the knight inside the 5 by 6 board is mapped and connected with edges.$
Determine if the closed knight’s tour in Figure 12.239 is most accurately described as an Euler circuit or a Hamilton cycle, or both, of the graph of all possible knight moves. Explain your reasoning.

Search

Text Color

Text Size

Margin Size

Font Type

Who Knew?

Icosian Game

Checkpoint

Example 12.33

Differentiating between Hamilton Cycles or Euler Circuits

Checkpoint

Your Turn 12.33

Factorials

Example 12.34

Evaluating Factorials

Your Turn 12.34

FORMULA

Example 12.35

Counting Arrangements of Letters

Your Turn 12.35

Counting Hamilton Cycles in Complete Graphs

FORMULA

Example 12.36

Counting Hamilton Cycles in a Complete Graph

Your Turn 12.36

Weighted Graphs

Example 12.37

Finding Hamilton Cycles of Lowest Weight

Your Turn 12.37

Check Your Understanding

Section 12.7 Exercises