Hamiltonian paths and cycles practice questions | General Mathematics (Year 11, VCE Units 1 & 2, Graphs and networks, Hamiltonian paths and cycles)

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 this route 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 condition

Rejecting 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{ can be a cycle if each consecutive pair is joined; the shared A is allowed}\)

The starting vertex is allowed to appear again as the final vertex of a Hamiltonian cycle

Inventing 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 sequences

Difficulty 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 the odd-degree test decide whether a Hamiltonian cycle exists?+

No. The odd-degree test is for Eulerian routes. For Hamiltonian routes, check candidate 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 11, VCE Units 1 & 2, General Mathematics, chapter 8: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula 8C Euler's formula: A full network investigation Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification 8E Eulerian trails and circuits: A full network investigation Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection 8G Weighted graphs and shortest paths: A full network investigation Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms 8H Trees and minimum spanning trees: A full network investigation