Hamiltonian paths and cycles
Hamiltonian routes are tested by vertex coverage rather than by using every edge. A path is open, while a cycle returns to its start after visiting each vertex once
\[|V_{\text{route}}|=|V(G)|\]
- Visit every vertex once A Hamiltonian path visits every vertex exactly once \(\displaystyle A\!-!B\!-!C\!-!D\)
- Allow the cycle return A Hamiltonian cycle returns to its starting vertex after visiting every vertex once \(\displaystyle A\!-!B\!-!C\!-!D\!-!A\)
- Leave edges unused A Hamiltonian route need not use every edge in the graph \(\displaystyle E_{\text{route}}\subseteq E(G)\)
- Test routes systematically There is no simple degree rule that decides whether a Hamiltonian route exists \(\displaystyle \text{degree counts alone}\not\Rightarrow\text{Hamiltonian route}\)
Worked example
A graph has vertices A, B, C, D and E and edges AB, BC, CD, DE, EA, AC and BD. Is the route shown a Hamiltonian cycle?
\[V=\{A,B,C,D,E\},\quad E=\{AB,BC,CD,DE,EA,AC,BD\},\quad A\!-!B\!-!C\!-!D\!-!E\!-!A\]
- \(\displaystyle A\!-!B\!-!C\!-!D\!-!E\!-!A\)Each consecutive pair in the route is an edge in the graph
- \(\displaystyle |\{A,B,C,D,E\}|=5=|V|\)The route visits all five vertices
- \(\displaystyle A\text{ is the shared start and end}\)A Hamiltonian cycle permits the starting vertex to appear at the end
- \(\displaystyle \text{Hamiltonian cycle}\)The route is a Hamiltonian cycle
Common mistakes
Using edge coverage
✕\(\displaystyle \text{Hamiltonian}\Rightarrow\text{use every edge exactly once}\)✓\(\displaystyle \text{Hamiltonian}\Rightarrow\text{visit every vertex exactly once}\)
Hamiltonian routes are defined by vertex coverage, whereas using every edge exactly once is an Eulerian conditionRejecting the return to the start
✕\(\displaystyle A\!-!B\!-!C\!-!D\!-!A\text{ is not a cycle because A repeats}\)✓\(\displaystyle A\!-!B\!-!C\!-!D\!-!A\text{ is a cycle; the shared A is allowed}\)
The starting vertex is allowed to appear again as the final vertex of a Hamiltonian cycleInventing a degree rule
✕\(\displaystyle \text{odd-degree count}=0\Rightarrow\text{Hamiltonian cycle exists}\)✓\(\displaystyle \text{No simple degree rule; test adjacent candidate routes}\)
Degree parity gives Eulerian conditions, but Hamiltonian routes require systematic checking of vertex sequencesDifficulty levels
introSelect a Hamiltonian path on a small graph and check vertex coverage
standardSelect a Hamiltonian cycle and account for the permitted return to the start
challengeUse a pendant-vertex obstruction or select a Hamiltonian route on a larger graph
examSelect the listed route that satisfies the Hamiltonian path or cycle conditions
Questions about this topic
What is the difference between a Hamiltonian path and a Hamiltonian cycle?+
A Hamiltonian path visits every vertex exactly once and has different endpoints. A Hamiltonian cycle also visits every vertex once, then returns to its starting vertex
Can a Hamiltonian route leave edges unused?+
Yes. Hamiltonian conditions concern the vertices, so edges not needed by the route may remain unused
Can vertex degrees alone prove that a Hamiltonian cycle exists?+
No. There is no simple degree rule for Hamiltonian existence. Candidate routes must be checked for adjacency and vertex coverage
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks
In this chapter
Count the vertices, edges and loops of a graphDegrees, the degree sum, and even and odd verticesGraph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsPlanar graphs and drawings in planar formFaces and Euler's formulaRepresent a network in a matrixIdentify the network a connection matrix describesClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cyclesRead a weighted graphThe shortest path by inspectionDijkstra's algorithm for shortest distances and routesTrees and spanning treesMinimum spanning trees by Prim's and Kruskal's algorithmsA full network investigation