Hamiltonian Path

Hamiltonian Path
Field: Graph Theory
Image Created By: Jorin Schug

Hamiltonian Path

In Graph Theory, a Hamiltonian path is a series of vertices and edges such that every vertex is included only once.

Basic Description

All graphs have vertices and edges. Now, imagine traveling from vertex to vertex along the edges. We can mathematically characterize this "trip around the graph" with a list in order of the vertices and edges that make up the "trip". This series of vertices and edges is called a walk. In a walk, there are very few restrictions, so the edges or vertices can be visited any number of times. A walk where a vertex is not repeated is a called a path. A Hamiltonian path visits all the vertices exactly once.

If we extend a Hamiltonian path to connect the ending vertex to the starting vertex by means of an existing edge, then we have created something new—a Hamiltonian cycle. A cycle is a walk that connects back to its starting vertex, while a Hamiltonian cycle must hit all of the vertices exactly once before coming back to the starting vertex. If a graph has a Hamiltonian cycle, then it is called a Hamiltonian graph.

Mathematicians have not yet found a simple and quick way to find Hamiltonian paths or cycles in any graph, but they have developed some ideas that make the search easier. The More Mathematical Explanation lays out some of the theorems that determine whether a graph is Hamiltonian or not, as well as a discussion of the NP-completeness of finding Hamiltonian paths.

A More Mathematical Explanation

[Click to view A More Mathematical Explanation]

Theorems

There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. [...]

[Click to hide A More Mathematical Explanation]

Theorems

There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. For some simpler graphs, it can be done by hand. However, with larger graphs, a direct inspection of the graph will not provide a solution quickly. Furthermore, if a Hamiltonian path or cycle didn't exist, a mathematician would have to exhaust all of the possible paths to prove it. That could surely take a lifetime for large and difficult graphs. As a result, many theorems were developed to help find the existence of a Hamiltonian cycle and path. Two useful theorems (Dirac from 1952, and Bondy-Chvatal from 1974) are presented below.

Dirac's Theorem

If simple graph G has n ≥ 3 vertices and m ≥ n/2, where m is the minimum vertex degree in G, then G is a Hamiltonian graph. In words, if the graph has three vertices or more, and the degree of the vertex with the smallest degree is greater than half the number of vertices, then the graph has a Hamiltonian cycle.

Proof

[show more][hide]

If this proof is confusing, then there is a particular example below which illustrates all the concepts of the proof.

In this proof, n denotes the total number of vertices and m represents the lowest vertex degree of the graph. For other helpful terms and concepts, consult the page about the basics of Graph Theory.

An example maximal non-Hamiltonian graph G, with n = 8, to show the definitions of uv, S, and T.

We will prove Dirac's Theorem by assuming it is incorrect, and finding a contradiction. So, assume that there exists a non-Hamiltonian graph such that n ≥ 3 and m ≥ n/2. Now, we specially define a graph and sets of vertices in that graph in a particular way so that the result will almost be in plain sight.

First, let a simple graph G be a maximal non-Hamiltonian graph. In a maximal non-Hamiltonian graph, adding any new edge between two non-adjacent vertices would make the graph Hamiltonian. Let u and v be two non-adjacent vertices in G, and to make a Hamiltonian cycle, we add the new edge uv. This new graph has a name G + uv, since we are adding an edge to vertices u and v to make a Hamiltonian cycle. This Hamiltonian cycle would start at u, come around to v and then go straight to u through the new edge uv. Remember, since this graph is simple, it has no loops or multiple edges.

Thus, since G is non-Hamiltonian, any Hamiltonian cycle in G + uv must go through the edge uv, because it is the only edge that can complete the cycle. Since vertices u and v must be part of a Hamiltonian cycle, we can also define a Hamiltonian path in G that begins at u and ends at v. The path would just be the cycle without the final edge uv. Let's call this path uv₁v₂...v. We will make more definitions based on this path.

Second, we consider two sets of vertices. We define the set S to be all of the vertices such that the next vertex along the path has an edge connecting it with the vertex u in the graph G (not G + uv). This edge does not necessarily have to be in the Hamiltonian path, but it just has to connect to the vertex u. In math language, that looks lik this:

$S = \{v_{i} | uv_{i + 1} \in E\}$

where E is the set of all edges in G. Remember, the vertex u is the beginning of the Hamiltonian path. The set T is defined similarly. T is all of the vertices that have edges connecting them to the vertex v in G, which is the last vertex of the path. In math language:

$T = \{v_{i} | v_{i}v \in E\}$.

Note that we are only considering edges in the graph G, not in G + uv. Finally, to add a little extra notation, we say that S ∪ T is all the vertices that are in either S or T. S ∩ T is all of the vertices that are in both S and T. To denote the number of objects in a set, mathematicians use an absolute value sign. For example, |S| is the number of vertices in the set S.

By this defintion,

$|S| + |T| = |S\cup T| + |S\cap T|$

This is true because the union of the two sets does not take into account the fact that there are doubles of the vertices that S and T have in common. So the intersection must be added to take the doubles into account.

Now all of these names and definitions will actually get us somewhere!

We know that

$v \notin S\cup T \Rightarrow |S\cup T| < n.$

The vertex v is not in T because G is a simple graph. The vertex does not border itself, since there can be no loops, and the edge uv does not exist in G. Thus v meets neither definition of S or T, and so:

$|S\cap T| = 0.$

This is because if a vertex were in both S and T, we could create a Hamiltonian cycle in G. To make this supposed cycle, we assume that some vertex v_i is in both S and T. Thus it is adjacent to T, and the next vertex along the path, v_{i + 1} is adjacent to u. So we can construct a Hamiltonian cycle with the vertex sequence uv₁...v_ivv_{n - 1}...v_{i + 1}u. The existence of this path is forbidden by our assumption, so no such v_i exists.

Now we also know that, by definition,

$|S| = d(u)$ and $|T| = d(v)$

For the final step, we consider d(u) + d(v). By substitution,

$d(u) + d(v) = |S| + |T|$

$d(u) + d(v) = |S \cup T| + |S \cap T|$

$d(u) + d(v) = |S \cup T|$

$d(u) + d(v) < n$

So d(u) + d(v) < n. But this contradicts the fact m ≥ n/2, because

$d(u) > \frac{n} {2} \Rightarrow d(v) < \frac{n} {2}$

Since either d(u) or d(v) has to be less than n/2, then m is definitely less than n/2. This contradicts our assumption that m ≥ n/2. We have found it is impossible for non-Hamiltonian graphs to have m ≤ n/2 and n ≥ 3. This clearly contradicts the original assumption. Since we have found the contradiction in the negation of Dirac's Theorem, we have proved the truth of Dirac's Theorem!

An Example

[show more][hide]

(Image 1) A simple non-Hamiltonian graph G, and a Hamiltonian graph G + 34

We can use the graph G in Image 1 to grasp how this theorem works using numbers instead of variables. G only requires one more edge to be Hamiltonian, an edge that goes from vertex 3 to vertex 4. In G we have the Hamiltonian path 4123, where our starting vertex is 4, and our ending vertex is 3. The graph with the extra edge is called G + 34. So our Hamiltonian cycle in G + 34 would be 41234.

Now, for the graph G, our m = 1, since d(4) = 1, and n= 4, since we have four vertices. Then m ≤ n/2 = 2, and G is non-Hamiltonian, which we can see in the picture. However, when we add 34, m = 2 now. And in fact m ≥ n/2 for this new graph, and it is now Hamiltonian. This discovery follows the theorem, and we have shown that it works for this example. Since Dirac's Theorem is only an "if-statement", the theorem actually tells us nothing about graphs that do not meet its conditions, such as G. It was convenient this time that G was not Hamiltonian when it did not meet the conditions.

However, this simple method could not be employed in the proof, since we had no exact numbers to work with. This is only one case. The theorem needs to be proved for a general case. The following uses the exact same method as the proof, but it is only applied to this one graph. It is meant to show the ideas of the proof without having to use too many variables.

[show more][hide]

Let us assume that the theorem is wrong and then show that a contradiction arises.

Since the path starts at 4 and ends at 3, vertex 3 would play the part of the u and vertex 4 would play the part of v (as a note for those who read the proof).

In the general case the degree of a vertex could not be found by inspection. Instead we had to use alternate means. That method will now be shown on our example graph, with the same results as the above analysis.

First, we need to define two groups of vertices.

• We call a set S all the vertices such that the next vertex along the path shares an edge with the first vertex in the cycle in G.
  • In this example, it would be all of the vertices whose successor shares an edge with vertex 4, since 4 is our starter. We can tell that the set S thus only contains 4.
• Our set T is all of the vertices that share an edge with the last vertex in the cycle in G.
  • In this case, the last vertex is 3, and T contains 2 and 1.

At this point in the proof, we showed that the last vertex in the Hamiltonian path of G was not a member of either set, since it is not adjacent to itself or the first vertex. In this case, that corresponds to 3 not being in either S or T since it is not adjacent to itself or 4. This means that there are fewer vertices in both the sets than there are vertices total.

The next step was to show that S and T have no vertices in common. In this case, this is also true, since S is just 4, and T is just 2 and 1.

Finally, we showed that the degree of the starting vertex is the same as the number of vertices in the set S, and the degree of the ending vertex is the same as the number of vertices in the set T. In the example, S has 1 element, and d(4) = 1. T has 2 elements, and d(3) = 2. Furthermore, adding the number of total elements in both sets is the same as adding the number of elements that the two sets have together and the ones they have in common. Here in the example, this amounts to one element in S plus 2 elements in T equals 3 distinct elements total plus 0 elements in common. 1 + 2 = 3 + 0.

So now, it is a simple matter of substitution. It is true that the sum of the degrees is 1 + 2. Using the facts we showed above, 1 + 2 = 3 + 0 = 3. This last number we know for a fact is less than the total number of vertices, 3 < 4. Since 1 + 2 < 4, we know that m must be less than n/2. Namely, 1 < n/2 = 2. This contradicts the negation of the theorem! By the negation, m should be greater than or equal to 2. But it isn't! So thus, the theorem is correct in this case.

Since in the general proof, all of these numbers were replaced with variables, we had to use this very complex method.

Bondy-Chvátal Theorem

Let G be a simple graph and let n be the number of vertices in G. Let u and v be two nonadjacent vertices in G such that d(u) + d(v) ≥ n. Then G is Hamiltonian if and only if G + uv is Hamiltonian.

Proof

[show more][hide]

Since the theorem is of the form ''A if and only if B", it has to be proven both as A implies B and as B implies A. We start with showing that G being Hamiltonian implies that G + uv is Hamiltonian. This is true since no new vertices were added.

Now, it must be shown that if G + uv is Hamiltonian then G is Hamiltonian. This is another proof by contradiction. So, let us assume that there is some non-Hamiltonian graph G such that G + uv is Hamiltonian, where d(u) + d(v) ≥ n

In this case, repeat the proof for Dirac's theorem. This proof shows that d(u) + d(v) < n. However, this is contrary to how we picked u and v, namely d(u) + d(v) ≥ n. Thus we have a found a contradiction, and verified the truth of the Bondy-Chvátal theorem!

An Example

[show more][hide]

A simple non-Hamiltonian graph G, and an added edge 25. The Bondy-Chvátal theorem applies to this edge, since d(2) + d(5) ≥ 6.

Consider the graph to the right. First, we find two vertices such that the sum of their degrees is greater than or equal to the total number of vertices. Vertices 2 and 5 apply, since they are not already attached, and d(2) + d(5) = 3 + 3 = 6 ≥ 6 = n. So we add the edge 25 to the graph G. However, this graph is non-Hamiltonian because there is only one way we can get to vertex 1, and no way out. So no Hamiltonian cycle can be made in G + 25. Thus G + 25 is non-Hamiltonian and by the Bondy-Chvátal theorem, so is G.

Using the Two Theorems

Here is a graph with n =8 and m = 4. The Bondy-Chvátal theorem does not really help us, even though it applies. Dirac's theorem gives us a simple check for the existence of a Hamiltonian cycle.

Dirac's theorem is useful for simple graphs. For example, consider the graph in figure 1. Applying the Bondy-Chvátal theorem to this graph would not really help. Even though the theorem applies, one must still determine whether a Hamiltonian cycle is in this mess at all. However, Dirac's theorem provides a simple answer. A quick count of the vertices shows that n = 8 ≥ 3. Another quick inspection reveals that each vertex has a degree of 4, so m = 4. Since m = 4 ≥ 8/2 = n/2, Dirac's theorem applies, and this graph has a Hamiltonian cycle. Again, there is still the matter of finding the Hamiltonian cycle, but at least we now know one is there.

Unfortunately, Dirac's theorem applies to fewer graphs than the Bondy-Chvátal theorem. For example, consider the graph in the hidden example section. Dirac's Theorem does not apply since the minimum vertex degree is not greater than or equal to n/2, but Bondy-Chvátal works.

The Bondy-Chvátal theorem is an "if and only if" statement. Therefore, we can determine whether or not any graph is Hamiltonian, depending on its sole condition. Dirac's theorem is only an "if" statement. This means that the theorem does not apply to every graph. If the graph doesn't meet the theorem requirements that m ≥ n/2 and n = 2, then we cannot say anything about the graph at all.

Extension of the Bondy-Chvátal Theorem

There are extensions of the Bondy-Chvátal theorem that have great use for Hamiltonian paths. They relate to a new concept called the closure of a graph, denoted c(G).

To create the c(G), we need to consider all of the pairs of nonadjacent vertices u and v such that d(u) + d(v) ≥ n. Once all of these pairs are joined, c(G) has been created. The extension of the Bondy-Chvátal states that if c(G) is Hamiltonian then so is G. Surprisingly, this requires little proof. This is because the Bondy-Chvátal theorem applies to each new edge. We can thus apply that theorem recursively until we obtain c(G). More simply stated, if the Bondy-Chvátal theorem can add one helpful edge uv, there is no reason that we cannot add more. The closure of the graph is just a graph where all the helpful edges have been added.

In many cases, c(G) is a complete graph, one where each vertex is adjacent to every other. Complete graphs with three or more vertices are definitely Hamiltonian, since any necessary edge to complete the cycle is always present. Thus, if c(G) is complete, then G is Hamiltonian. This version of the theorem applies to the most cases and is the easy to calculate. For example, consider the graph in figure 2 again. Since the degree of every vertex is 4, then it clear that d(u) + d(v) = 4 + 4 = 8 ≥ n. So, by the extended Bondy-Chvátal theorem, we can make a new edge between every pair of non-adjacent vertices to make the closure of the graph c(G). This definitely creates a complete graph, and so the graph is Hamiltonian. This agrees with Dirac's theorem.

NP Completeness Proof

The full proof for the NP-completeness of finding a Hamiltonian path is long and difficult. However, the outline of those proofs are not as difficult. If it is known that problem A is NP-complete, and problem A can be transformed into problem B, then problem B is also NP-complete. This method doesn't have to be limited to only two problems. A whole chain of transformations can occur. This is exactly how finding a Hamiltonian path was shown to be NP-complete. The seed is a problem in logic, called Satisfiability. This problem involves finding a series of true statements such that the truth of larger statements is satisfied. This problem was proved NP-complete in 1972. This problem was then transformed into finding a chromatic number of a graph, then to finding an maximal independent set of vertices, then to finding a vertex cover of a graph, then to finding a digraph Hamiltonian path, and finally to finding a Hamiltonian path any graph. These transformations had been proved by 1985.

Why It's Interesting

Animation of a knight's tour

The Traveling Salesman problem solution has roots in finding Hamiltonian paths and cycles. In that problem, each edge of a graph has a number associated with it, called a weight. The salesman needs to take the Hamiltonian path or cycle with the lowest weight in order to minimize the cost of his travels. So once someone has an algorithm to find a Hamiltonian cycle, its a matter of finding the optimum cycle to solve the Traveling Salesman problem.

However, an algorithm for finding a Hamiltonian path or cycle can also be found from an algorithm for the Traveling Salesman problem.

To do this, take a graph G with n vertices and the complete graph with n vertices, called K_n. Since K_n is complete, G is a subgraph of it. So all the edges in G are also contained in the complete graph. Now, if an edge exists in G, we give it a weight of 0 in the complete graph. If it doesn't exist in G, give it a weight 1 in the complete graph. Now, we can apply our assumed Traveling Salesman algorithm to this complete graph. Any Hamiltonian path in the complete graph with a total weight of 0 will be a Hamiltonian path in G. Thus, a Hamiltonian path or cycle can be found with a Traveling Salesman algorithm. All the transformations of problems from one to another listed above in the NP-completeness section look something like this.

Another application of Hamiltonian paths is finding a knight's tour. The knight's tour is a challenge to have a knight move to every space on a chess board only once. It is the equivalent of finding a Hamiltonian path in the graph describing all the possible moves of the knight on the chessboard. As it turns out, this graph of knight's moves has a Hamiltonian path, as shown by the animation. In fact, both a Hamiltonian path and a Hamiltonian cycle can be found. There are 33,439,123,484,294 knight's tours on an 8 by 8 chess board.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

References

• Weisstein, Eric W. "Hamiltonian Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HamiltonianGraph.html
• Weisstein, Eric W. "Hamiltonian Cycle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HamiltonianCycle.html

Future Directions for this Page

• Maybe add more that is not in the more mathematical section
• more applications of Hamiltonian paths?
• There's a good applet here, find the terms of use for it?
• Create a Traveling Salesman Problem page -- not as a helper page, but a full-fledged page for extended explanation.
  

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.

  [[Description::In Graph Theory, a Hamiltonian path is a series of vertices and edges such that every vertex is included only once.|]]