Discrete Mathematics and Proof

Hamiltonian paths and cycles

A route that uses every road exactly once has a simple test. What about a round trip that stops at every place exactly once?

You need

Walks, paths, cycles and connected graphsDiscrete Mathematics and Proof

Where you are 10 in Introductory graph theory

Logic, proof and discrete math6

Introductory graph theory10

▴ 2 above Walks, paths, cycles and connected graphs Finding a shortest path

Hamiltonian paths and cycles

Planar graphs and Euler's formula Euler paths and circuits ▾ Show all 10 (3 more)

Why this exists

Kepa services weather beacons on hilltops joined by service roads. He wants a round trip that stops at every beacon exactly once and ends where it began. For a route using every road exactly once, Euler paths and circuits gives a complete answer read off the degrees. A route through every vertex looks like its twin, yet no such test is known: only tests that rule a tour out and conditions that guarantee one.

Definition

The notation is that of Degree, the handshake lemma and complete graphs and Walks, paths, cycles and connected graphs: G = (V, E) is a simple graph with n = \lvert V \rvert vertices and smallest degree \delta(G), and K_n and C_n are the complete graph and the cycle graph.

A Hamiltonian path in G is a path containing every vertex of G, (v_0, v_1, \ldots, v_{n-1}), each vertex appearing once. Its length is n - 1.
A Hamiltonian cycle is a cycle containing every vertex, (v_0, v_1, \ldots, v_{n-1}, v_0) with v_0, \ldots, v_{n-1} all the vertices. Its length is n, so n \ge 3. Two Hamiltonian cycles are the same exactly when they use the same edges.
G is Hamiltonian if it has a Hamiltonian cycle.
For a set S of vertices, G - S is what is left after deleting the vertices of S and every edge with an endpoint in S.
The m \times n grid has the mn vertices (i, j) with 1 \le i \le m (the row) and 1 \le j \le n (the column); two are adjacent when they agree in one coordinate and differ by 1 in the other. Here n counts columns, not vertices.
The cube graph Q_3 has the 8 binary strings of length 3 as vertices, two adjacent when they differ in exactly one place; Q_d uses the 2^d strings of length d.
A Gray code of length d lists all 2^d binary strings of length d so that each differs in exactly one place from the next, and the last from the first: a Hamiltonian cycle in Q_d.

The name honors William Rowan Hamilton, who made a puzzle of finding such a cycle along the edges of a dodecahedron.

Intuition

Figure 1Kepa’s map. Eight beacons and ten service roads; A, D, G and H each have only two roads.

A tour uses exactly two roads at every beacon, in and out. So a beacon with only two roads, such as A in Figure 1, forces both into every tour. And closing a few beacons breaks a tour into at most as many pieces as beacons closed.

Results

1. No simple test is known. Deciding whether a graph has a Hamiltonian cycle is an NP-complete problem: every known method takes time growing exponentially with n, and a fast one would give fast methods for many other hard problems. Whether one exists is a famous open question. Stated without proof.

2. Counting in K_n. For n \ge 3, K_n has exactly \displaystyle \frac{(n-1)!}{2} Hamiltonian cycles.

3. Degrees. If G is Hamiltonian, every vertex has degree at least 2, and a vertex of degree exactly 2 has both its edges in every Hamiltonian cycle.

4. Deleting vertices. If G is Hamiltonian and S is a set of k vertices with 1 \le k < n, then G - S has at most k components. If G has a Hamiltonian path, G - S has at most k + 1.

5. Odd grids. If mn is odd, the m \times n grid has no Hamiltonian cycle.

6. The cube. The list 000, 001, 011, 010, 110, 111, 101, 100 is a Gray code, so Q_3 is Hamiltonian (Example 5).

7. Dirac’s theorem. If G has n \ge 3 vertices and \displaystyle \delta(G) \ge \frac{n}{2}, then G is Hamiltonian.

8. Ore’s theorem. If G has n \ge 3 vertices and \deg(u) + \deg(v) \ge n for every two nonadjacent vertices u and v, then G is Hamiltonian. Stated without proof. It contains Dirac’s theorem, since \displaystyle \delta(G) \ge \frac{n}{2} makes every such sum at least n.

9. The Petersen graph of Figure 2 is not Hamiltonian. Stated without proof. Its outer vertices 0 to 4 form a pentagon, each i is joined to i + 5, and the inner edges are 57, 79, 96, 68, 85. Every degree is 3, and deleting any k of its vertices leaves at most k components: it passes Results 3 and 4 and still has no tour.

Figure 2The Petersen graph. Every vertex has degree 3, and there is no Hamiltonian cycle.

Why it is true

Result 2. Proof. Fix a vertex x. Every Hamiltonian cycle can be written from x as (x, v_1, \ldots, v_{n-1}, x), and in K_n every ordering of the other n - 1 vertices gives one, since every two vertices are adjacent: (n - 1)! sequences. Each cycle is written from x in exactly two ways, one per direction, which differ because v_1 \ne v_{n-1} when n \ge 3. So there are \displaystyle \frac{(n-1)!}{2} cycles. \square

Result 3. Proof. On a Hamiltonian cycle each vertex is joined to the vertex before it and the one after it, two different neighbors. If its degree is exactly 2, those two cycle edges are all its edges. \square

Result 4. Proof. Go once around the Hamiltonian cycle and delete the k vertices of S. The vertices left fall into runs of consecutive cycle vertices, each ending just before a vertex of S, a different one for each run; so there are at most k runs. Each run is a path in G - S, so it lies in one component, and every vertex of G - S is in a run. So G - S has at most k components. The path version is Exercise 12. \square

Result 5. Proof. Color (i, j) black when i + j is even and white when it is odd. An edge changes one coordinate by 1, so it changes the parity of i + j: every edge joins black to white. Along a cycle (v_0, v_1, \ldots, v_L = v_0) the colors alternate, so v_t has the color of v_0 exactly when t is even. Since v_L = v_0, L is even. A Hamiltonian cycle would have the odd length mn. \square

So a cycle has as many black vertices as white, and colors alternate along any path. Graphs colored this way are Bipartite graphs.

Result 7. Proof. First, G is connected. If u and v are not adjacent, each has at least \displaystyle \frac{n}{2} neighbors among the other n - 2 vertices, and \displaystyle \frac{n}{2} + \frac{n}{2} > n - 2, so by the pigeonhole principle they share a neighbor w, and (u, w, v) joins them.

There are finitely many paths, since none repeats a vertex; choose a longest, P = (v_0, v_1, \ldots, v_k). Every neighbor of v_0 or of v_k lies on P, or P could be made longer. As \displaystyle \deg(v_0) \ge \frac{n}{2} > 1, v_0 has at least two neighbors on P, so k \ge 2. Let

A = \{\, i : v_0 v_{i+1} \in E \,\}, \qquad B = \{\, i : v_i v_k \in E \,\}.

Both lie in \{0, 1, \ldots, k - 1\}, which has k \le n - 1 elements, while \displaystyle \lvert A \rvert = \deg(v_0) \ge \frac{n}{2} and \displaystyle \lvert B \rvert = \deg(v_k) \ge \frac{n}{2}. Since \lvert A \rvert + \lvert B \rvert \ge n > k, some i lies in both. Then v_0 v_{i+1} and v_i v_k are edges, and

C = (v_0, v_1, \ldots, v_i, v_k, v_{k-1}, \ldots, v_{i+1}, v_0)

is a cycle through all k + 1 vertices of P: out along P to v_i, across to v_k, back along P to v_{i+1}, and across to v_0.

Suppose k + 1 < n. As G is connected, a path from C to a vertex off C has a first step leaving C, so some w off C is adjacent to a vertex of C. Write C as (u_0, u_1, \ldots, u_k, u_0) with u_0 that neighbor. Then (w, u_0, u_1, \ldots, u_k) is a path of length k + 1, longer than P, a contradiction. So k + 1 = n, and C is a Hamiltonian cycle. \square

Worked examples

Example 1

Forced roads on Kepa’s map

Find every Hamiltonian cycle in Figure 1.

Solution

A, D, G, H have degree 2, so by Result 3 every Hamiltonian cycle uses AB, AF, CD, DH, CG, EG and FH. Now C already has its two cycle edges CD and CG, so BC is out; likewise F has AF and FH, so EF is out. That leaves B with only AB and BE, so BE is in. The eight chosen edges form

(A, B, E, G, C, D, H, F, A),

through all 8 beacons. Every edge was forced, so this is the only Hamiltonian cycle.

Example 2

Counting tours when every road exists

In Kepa’s first district, 6 beacons are joined in every pair by a road. How many tours are there? How many routes, if he starts at his base and the direction counts? How many tours would 15 such beacons have?

Solution

The district is K_6, and Result 2 gives \displaystyle \frac{5!}{2} = \frac{120}{2} = 60 tours. From the base, the other 5 beacons come in any of 5! = 120 orders, each tour driven in two directions. For 15 beacons there are \displaystyle \frac{14!}{2} = 43{,}589{,}145{,}600 tours, too many to check one by one when roads have lengths and the shortest is wanted (Weighted and directed graphs).

Example 3

Ruling out a tour

Show that the graph of Figure 3 has no Hamiltonian cycle, and find a Hamiltonian path.

Figure 3Deleting P and Q leaves three pieces, \{a, b\}, \{c\} and \{d, e\}.

Solution

Every degree is at least 2, so the first part of Result 3 rules nothing out. Take S = \{P, Q\}, so k = 2. Deleting P and Q keeps only ab and de, leaving components with vertex sets \{a, b\}, \{c\}, \{d, e\}. Since 3 > 2, Result 4 rules out a Hamiltonian cycle.

For a path, Result 4 allows k + 1 = 3 components, and indeed (a, b, Q, c, P, d, e) is a Hamiltonian path: ab, bQ, Qc, cP, Pd, de are all edges.

Example 4

A grid with an odd number of vertices

Show that the 3 \times 5 grid of Figure 4 has no Hamiltonian cycle, find a Hamiltonian path, and show that every Hamiltonian path starts and ends at black vertices.

Figure 4The 3 \times 5 grid. Filled (black) vertices have i + j even, open (white) ones i + j odd; every edge joins one of each.

Solution

There are 3 \cdot 5 = 15 vertices, an odd number, so Result 5 rules out a cycle. Snaking gives a path: row 1 from (1, 1) to (1, 5), down to (2, 5), row 2 back to (2, 1), down to (3, 1), and row 3 to (3, 5).

Rows 1 and 3 have black vertices in columns 1, 3, 5 and row 2 in columns 2, 4: 8 black and 7 white. Along a Hamiltonian path (v_0, \ldots, v_{14}) colors alternate, so the 8 vertices in even places, v_0 and v_{14} among them, share a color; only 7 are white, so it is black.

Example 5

A Gray code on the cube

Build a Gray code of length 3 from the Gray code 00, 01, 11, 10 of length 2, and trace it in Q_3.

Solution

Write 0 in front of each string of the length 2 code, then 1 in front of each string of the same code read backward:

000, 001, 011, 010, \quad 110, 111, 101, 100.

Inside each half, neighbors differ in one place, because the length 2 code did. At the seam, 010 and 110 differ only in the first place, as do the last string 100 and the first 000. All 8 strings appear once, so this is a Gray code: the solid cycle of Figure 5.

Figure 5The Gray code 000, 001, 011, 010, 110, 111, 101, 100 is the solid Hamiltonian cycle in Q_3.

Example 6

Dirac’s theorem and its limits

(a) Kepa’s network grows to 12 beacons, each with roads to at least 6 others. Show that a tour exists, whatever the roads are. (b) Show that 11 beacons each with roads to at least 5 others need not have one. (c) Does a tour need Dirac’s condition?

Solution

(a) Here n = 12 \ge 3 and \displaystyle \delta(G) \ge 6 = \frac{12}{2}, so Dirac’s theorem applies.

(b) Take two copies of K_6 sharing one vertex s: 6 + 6 - 1 = 11 vertices, s of degree 10 and the rest of degree 5. Deleting s leaves two components with k = 1, so by Result 4 there is no Hamiltonian cycle. Here \displaystyle \delta = 5 = \frac{n - 1}{2}: the bound \displaystyle \frac{n}{2} cannot be lowered to \displaystyle \frac{n - 1}{2}.

Example 7

Closing a path into a cycle

A graph on 8 vertices with \delta \ge 4 contains the path (v_0, v_1, \ldots, v_7). The neighbors of v_0 are v_1, v_3, v_5, v_6, and those of v_7 are v_1, v_2, v_4, v_6. Follow the proof of Dirac’s theorem to close the path into a Hamiltonian cycle.

Solution

The path has all 8 vertices, so it is longest, with k = 7. As v_0 v_{i+1} is an edge for i + 1 = 1, 3, 5, 6, A = \{0, 2, 4, 5\}; likewise B = \{1, 2, 4, 6\}. Both lie in \{0, \ldots, 6\} and 4 + 4 = 8 > 7, so they meet: A \cap B = \{2, 4\}. With i = 2 the edges v_0 v_3 and v_2 v_7 give

(v_0, v_1, v_2, v_7, v_6, v_5, v_4, v_3, v_0),

and with i = 4 the edges v_0 v_5 and v_4 v_7 give

(v_0, v_1, v_2, v_3, v_4, v_7, v_6, v_5, v_0).

Both are Hamiltonian cycles.

Boundaries

The tests only rule out. Results 3, 4 and 5 are necessary conditions; the Petersen graph passes Results 3 and 4 and has no tour.
The guarantees only guarantee. Dirac’s and Ore’s conditions are sufficient, not necessary: C_n and Q_3 are Hamiltonian with small degrees.
At least three vertices. K_2 has \displaystyle \delta = 1 = \frac{n}{2} and no cycle, since a cycle needs 3 vertices.
Grids. Result 5 concerns cycles only. Its converse needs m, n \ge 2 (Exercise 13): a 1 \times n grid has vertices of degree 1.

Where this goes next

The coloring of Result 5 becomes Bipartite graphs. Costs on roads lead to Weighted and directed graphs and Finding a shortest path. Being Hamiltonian survives relabeling, which helps in Graph isomorphism: when two drawings are the same graph.

Exercises

Finding and counting

In Figure 1, find a Hamiltonian path from A to C, or show that none exists.
Find a Hamiltonian path in the Petersen graph of Figure 2.
How many Hamiltonian cycles does K_7 have? How many Hamiltonian paths does K_5 have, a path and its reverse counting as one?
Find a Gray code of length 3 that begins 000, 100, 110.
Apply the construction of Example 5 to the code of Result 6 to get a Gray code of length 4.

Ruling tours out

Does each graph have a Hamiltonian cycle? A Hamiltonian path? (a) Two triangles sharing one vertex; (b) three triangles sharing one vertex; (c) C_5 with one extra edge.
In the 3 \times 3 grid, at which vertices can a Hamiltonian path start? Give a path from each kind of starting vertex.
Does the 4 \times 6 grid have a Hamiltonian cycle? Does the 5 \times 7 grid?
Delete one vertex from the 3 \times 3 grid. Is what remains Hamiltonian when the deleted vertex is (a) (1, 2); (b) (1, 1)?

Guaranteeing a tour

Vertices a, b, c, d are all joined to each other, and a fifth vertex x is joined to a and b only. Show that Dirac’s theorem does not apply but Ore’s does, and find a Hamiltonian cycle.

Reasoning

Prove that for n \ge 2, K_n has \displaystyle \frac{n!}{2} Hamiltonian paths, a path and its reverse counting as one.
Prove the second half of Result 4: if G has a Hamiltonian path and S is a set of k vertices with 1 \le k < n, then G - S has at most k + 1 components.
Prove that if m, n \ge 2 and mn is even, the m \times n grid is Hamiltonian.
Prove by induction that Q_d is Hamiltonian for every d \ge 2.
Use Ore’s theorem to prove that a graph with n \ge 3 vertices and at least \binom{n-1}{2} + 2 edges is Hamiltonian. Show that \binom{n-1}{2} + 1 edges are not enough.
Refute with a counterexample: “every connected graph in which every vertex has degree at least 2 is Hamiltonian.” Do not use the Petersen graph.

Answers

None. D and G lie inside such a path, so each uses both its edges, including CD and CG. Then the endpoint C has two path edges, but an endpoint has one.
One answer: (0, 1, 2, 3, 4, 9, 7, 5, 8, 6), using the pentagon, the spoke 49 and the inner edges 97, 75, 58, 86.
\displaystyle \frac{6!}{2} = 360 cycles. Paths in K_5: \displaystyle \frac{5!}{2} = 60, by Exercise 11.
One answer: 000, 100, 110, 010, 011, 111, 101, 001; each differs from the next in one place, and 001 from 000.
0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, then 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
(a) A path, no cycle: with triangles c, x, y and c, z, w, take (x, y, c, z, w); deleting c leaves 2 > 1 components. (b) Neither: deleting the shared vertex leaves 3 > 1 + 1 components. (c) Both: C_5 is a Hamiltonian cycle.
At the 5 black vertices, the corners and the center. A path of 9 alternates colors, so with 5 black and 4 white it starts and ends black. From a corner, snake the rows. From the center: (2, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3).
The 4 \times 6 grid does: row 1 from (1, 1) to (1, 6), row 2 from (2, 6) to (2, 2), row 3 from (3, 2) to (3, 6), row 4 from (4, 6) to (4, 1), then (3, 1), (2, 1), (1, 1). The 5 \times 7 grid does not: 35 is odd.
(a) No. (1, 2) is white, so 5 black and 3 white remain, but a cycle has as many of each. (b) Yes: (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (2, 1), (2, 2), and back to (1, 2).
\displaystyle \deg(x) = 2 < \frac{5}{2}, so Dirac’s theorem does not apply. The nonadjacent pairs are x, c and x, d, with degree sums 2 + 3 = 5 = n, so Ore’s does. A cycle: (x, a, c, d, b, x).
Proof. Every ordering of the n vertices is a Hamiltonian path in K_n: n! orderings. Each path is two of them, one per direction, which differ because the first and last vertices differ when n \ge 2. \square
Proof. As in Result 4, delete S from the path. Every run of remaining vertices but the last ends just before its own vertex of S, so there are at most k + 1 runs, and each lies in one component of G - S. \square
Proof. Swapping rows and columns if needed, let m be even. Go along row 1 to (1, n), then snake through rows 2 to m - 1 in columns 2 to n, leftward first; m - 2 is even, so the snake ends at (m - 1, n) (for m = 2 it is empty). Go along row m from (m, n) to (m, 1) and climb column 1 to (1, 1), as in Exercise 8. Every vertex appears once and each step is an edge. \square
Proof. For d = 2, 00, 01, 11, 10 is a Gray code. If s_1, \ldots, s_N is a Gray code of length d, then 0s_1, \ldots, 0s_N, 1s_N, \ldots, 1s_1 lists all strings of length d + 1 once; neighbors inside each half differ where the old ones did, and the pairs 0s_N, 1s_N and 1s_1, 0s_1 differ only in the first place. \square
Proof. If all pairs are adjacent, G = K_n is Hamiltonian. Otherwise let u, v be nonadjacent. At most \binom{n-2}{2} edges avoid both, and \deg(u) + \deg(v) edges meet one, since uv is not an edge. So \deg(u) + \deg(v) \ge \binom{n-1}{2} + 2 - \binom{n-2}{2}, which is (n - 2) + 2 = n, and Ore’s theorem applies. K_{n-1} plus a vertex joined to one of its vertices has \binom{n-1}{2} + 1 edges and a vertex of degree 1, so it is not Hamiltonian. \square
Two triangles x, y, z and x', y', z' joined by the edge zx'. It is connected with every degree at least 2, but deleting z leaves 2 > 1 components, so by Result 4 it is not Hamiltonian.