Spanning Routes Through a Graph
A path or cycle can use only some of a graph’s vertices. Hamiltonian paths and cycles are the versions that use every vertex. The distinction is about coverage: a long path need not be Hamiltonian if even one vertex is omitted, while a short cycle inside a larger graph is an ordinary cycle but not a Hamiltonian cycle. In this tutorial, all graphs are finite and simple: they have no loops or multiple edges.
A walk is a sequence of vertices in which consecutive vertices are joined by an edge. A path is a walk with no repeated vertices. A cycle is a closed sequence \(v_0,v_1,\ldots,v_{k-1},v_0\), where \(k\ge 3\), the first \(k\) vertices are distinct, and each consecutive pair, including \(v_{k-1},v_0\), is an edge. Thus a cycle returns to its starting vertex, but does not repeat any other vertex. A path or cycle is not required to include every vertex of the graph.
The word “Hamiltonian” does not change the adjacency rule for paths or cycles. It adds the requirement that the sequence covers the entire vertex set. For a graph of order \(n=|V|\), a Hamiltonian path has \(n\) distinct vertices and \(n-1\) edges. A Hamiltonian cycle has \(n\) distinct vertices and \(n\) edges, with the final edge returning from the last listed vertex to the first. These counts follow directly from the definitions; they are useful checks, but do not by themselves establish that a proposed sequence works.
How to Check a Proposed Sequence
To check a proposed Hamiltonian path, first confirm that every consecutive pair in the sequence is an edge. Then check that no vertex repeats and that the set of listed vertices is all of \(V\). For a proposed Hamiltonian cycle, make the same checks and also verify the edge from the last listed vertex back to the first. The return to the start is part of the cycle, not an optional extra.
It is helpful to keep the three checks separate. A sequence can use only edges of the graph and still fail because it misses a vertex. It can list every vertex and still fail because one consecutive pair is not adjacent. And a sequence that traces a path through all vertices does not automatically give a cycle: the endpoints must also be joined by an edge.
Worked Example: A Hamiltonian Cycle in a Five-Vertex Graph
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13\}\). Test the sequence \(1,2,3,4,5,1\) as a Hamiltonian cycle.
Check the successive edges in order. The pair \(1,2\) is the edge \(12\); \(2,3\) is \(23\); \(3,4\) is \(34\); and \(4,5\) is \(45\). The closing pair \(5,1\) is \(51\). Thus every required edge is in \(E\).
The distinct vertices before returning to the start are \(1,2,3,4,5\). This list has five entries, no repetitions, and its set is exactly \(V\). The sequence therefore is a cycle that contains every vertex: it is a Hamiltonian cycle. Its five cycle edges are \(12,23,34,45,51\); the remaining edge \(13\) is not needed for this particular cycle.
Check: The graph has five vertices, and the proposed cycle uses five distinct vertices and five listed edges, including the closing edge. Each of those five edges appears in the specified edge set, so the answer satisfies both adjacency and coverage.
How Hamiltonian Paths and Cycles Relate
Proof. First suppose that \(G\) has a Hamiltonian cycle \(v_0,v_1,\ldots,v_{n-1},v_0\), where \(n=|V|\ge 3\). Delete the closing edge \(v_{n-1}v_0\) from this sequence. The remaining sequence \(v_0,v_1,\ldots,v_{n-1}\) still has every consecutive pair adjacent, has no repeated vertices, and contains every vertex of \(G\). It is a Hamiltonian path. Reversing a Hamiltonian path \(v_0,v_1,\ldots,v_{n-1}\) gives \(v_{n-1},\ldots,v_1,v_0\); its consecutive pairs are the same edges in reverse order, and it still lists every vertex exactly once.
For the stated equivalence, the forward direction follows from the cycle just considered: deleting its closing edge leaves a Hamiltonian path whose endpoints \(v_0\) and \(v_{n-1}\) are adjacent by that deleted edge. Conversely, suppose \(v_0,v_1,\ldots,v_{n-1}\) is a Hamiltonian path and \(v_0v_{n-1}\in E\). Its vertices are all distinct and cover \(V\). The given path edges, followed by the edge \(v_{n-1}v_0\), form a cycle. Since \(n\ge 3\), this cycle has at least three distinct vertices and meets the definition of a Hamiltonian cycle. \(\square\)
This equivalence makes the endpoint check precise: a Hamiltonian path is a route covering the vertices; it closes into a Hamiltonian cycle exactly when its endpoints are adjacent. It does not say that every Hamiltonian path in a graph can be closed. The required endpoint edge must actually belong to \(E\).
Worked Example: A Hamiltonian Path but No Hamiltonian Cycle
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). The sequence \(1,2,3,4\) is a path: its consecutive pairs \(12,23,34\) are all edges. Its vertices \(1,2,3,4\) are distinct and equal to the full vertex set, so it is a Hamiltonian path. Its endpoints are \(1\) and \(4\), but \(14\notin E\), so this particular path does not close.
To check whether there is some other Hamiltonian cycle, list the possible cycles on these four vertices, counting a cycle and its reverse as the same cycle. Starting at \(1\), there are three choices of order for the other vertices up to reversal:
- \(1,2,3,4,1\) would require the edge \(41\), which is absent.
- \(1,2,4,3,1\) would require the edge \(24\), which is absent.
- \(1,3,2,4,1\) would require the edges \(24\) and \(41\), both absent.
These are all three cyclic orders: fixing \(1\) first leaves six orders of \(2,3,4\), and reversing direction pairs them into three. None gives a cycle in \(G\). The graph therefore has a Hamiltonian path but no Hamiltonian cycle.
Check: The ordinary cycle \(1,2,3,1\) is present because \(12,23,31\in E\), but it is not Hamiltonian: it omits vertex \(4\). This confirms that an ordinary cycle in the graph is not enough to establish a Hamiltonian cycle.
Worked Example: A Path That Cannot Cover Two Separated Groups
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,45\}\). The sequence \(1,2,3\) is an ordinary path, and \(4,5\) is another ordinary path. Neither sequence is Hamiltonian because the first omits \(4,5\) and the second omits \(1,2,3\).
There is no Hamiltonian path. Indeed, the listed edges have no endpoint in \(\{1,2,3\}\) joined to a vertex in \(\{4,5\}\). A path containing all five vertices would have to list vertices from both sets in one sequence. At the point where the sequence first passes from one set to the other, two consecutive vertices from different sets would have to be adjacent. No such edge is in \(E\), so this cannot be a path.
There is also no Hamiltonian cycle: such a cycle would in particular be a path through all five distinct vertices in cyclic order, and that order would still need an edge joining the two sets. The edge list contains no such edge.
Check: The only edges are \(12\), \(23\), and \(45\). Each has both endpoints in one of the two displayed sets, so the proposed transition between sets is impossible. The sequence \(1,2,3,4,5\), for example, fails exactly at the pair \(3,4\), since \(34\notin E\).
Common Mistakes and Why the Distinction Matters
Confusing “a cycle” with “a Hamiltonian cycle.” In the four-vertex example, \(1,2,3,1\) is a cycle, but it does not cover vertex \(4\). A cycle is Hamiltonian only when its distinct vertices before returning to the start are precisely the full vertex set.
Forgetting the closing edge. A sequence \(v_0,\ldots,v_{n-1}\) that is a Hamiltonian path need not be a Hamiltonian cycle. To close it, the edge \(v_{n-1}v_0\) must be present. In the four-vertex example, the displayed Hamiltonian path has endpoints \(1\) and \(4\), and \(14\) is not an edge.
Counting the return to the start as a new vertex. In a cycle \(v_0,\ldots,v_{n-1},v_0\), the last occurrence of \(v_0\) records the return along an edge. It is not an additional distinct vertex. The cycle contains \(n\) distinct vertices and \(n\) edges, not \(n+1\) distinct vertices.
Hamiltonian paths and cycles describe routes that visit every vertex once, so they model tasks where all locations must be visited without repetition. The definitions alone do not provide a quick test for every graph. For a proposed sequence, however, the checks are direct: verify its edges, distinct vertices, and full coverage; for a cycle, verify the closing edge too. The examples show why these checks must be kept separate.
Check Your Understanding
For each question, use the stated vertex and edge sets and check the relevant sequence against the definitions.
- Let \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,da\}\). Is \(a,b,c,d\) a Hamiltonian path? Is it a Hamiltonian cycle?
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,13\}\). Identify one ordinary cycle and decide whether it is Hamiltonian.
- For a Hamiltonian path \(v_0,\ldots,v_{n-1}\), what additional edge is required for this same sequence to give a Hamiltonian cycle?
- Explain why the empty graph has no Hamiltonian path under the convention used here, while a graph with one vertex does have one.
- Give the distinct-vertex list and the closing edge for the cycle \(2,4,1,3,2\), and state what must be checked before calling it Hamiltonian in a specified graph.