COMP2121 Chap.10 Hamiltonian Paths and Circuits
Hamiltonian Paths and Circuits
No simple test
Hamiltonian paths and circuits visit every vertex exactly once. Unlike the Euler question, deciding whether one exists has no simple criterion and is NP-hard.
Some families always have one: every tournament has a Hamiltonian path, proved by inserting each new player into an existing path.
Obstructions and sufficient conditions
Non-existence is shown by structure: unequal sides of a bipartite graph, an independent set larger than half the vertices, or forced edges at low-degree vertices.
Dirac's and Ore's theorems give sufficient conditions for a circuit, and the travelling salesman problem asks for the cheapest one.
Using an independent set as an obstruction
A Hamiltonian circuit on n vertices visits them in a cycle, and no two consecutive vertices of an independent set can be adjacent on it. So an independent set can contain at most half the vertices of a graph with a Hamiltonian circuit.
When a graph has an independent set larger than n over 2, no circuit exists.
The bipartite imbalance test is a special case: the larger side of a bipartite graph is an independent set.
Using the sufficient conditions correctly
Dirac's theorem asks for a simple graph on at least three vertices with every degree at least n over 2. Ore's theorem is weaker in its demand, asking only that every pair of non-adjacent vertices has degrees summing to at least n.
Both guarantee a circuit, and neither says anything when it fails. A graph that misses both conditions may still have a circuit, which must then be shown by construction.
What this chapter covers
- 01
Hamiltonian paths and circuits
- 02
Tournaments
- 03
Bipartite imbalance
- 04
Independent sets and forced edges
- 05
Dirac's and Ore's theorems
- 06
Travelling salesman problem
Worked example · free
Insert a player into a tournament path
- 2Find the first player on the path that e beats.
- 2Insert e just before that player.
- 1Check every arc on the new path.
Key terms
- Hamiltonian circuit
- A circuit that visits every vertex of a graph exactly once.
- Tournament graph
- A directed graph with exactly one arc joining each two different vertices.
- Independent set
- A set of vertices no two of which are adjacent.
Hamiltonian Paths and Circuits FAQ
Is there a degree test for Hamiltonian circuits?
No simple necessary and sufficient test exists, and deciding the question is NP-hard. Dirac's and Ore's theorems are sufficient conditions only, so a graph that fails them may still have a circuit.
How do I prove a graph has no Hamiltonian circuit?
Use an obstruction: a bipartite graph with unequal sides, an independent set with more than half the vertices, a vertex of degree one, or edges forced by degree-two vertices that close a short cycle.
How many Hamiltonian circuits does a complete graph have?
Counting a circuit by its set of edges, the complete graph on n vertices has n minus 1 factorial over 2 of them, since fixing a start leaves orders of the rest and each circuit has two directions.
Does every tournament have a Hamiltonian circuit?
No. Every tournament has a Hamiltonian path, but a circuit needs more. A tournament in which one player beats everyone has no circuit, because no arc returns to that player from the end of the path.
How is the travelling salesman problem related?
It asks for the cheapest Hamiltonian circuit in a complete graph with weighted edges. Since deciding whether any Hamiltonian circuit exists is already hard, no efficient general method for the cheapest one is known. For small graphs, listing the n minus 1 factorial over 2 circuits and comparing their weights works.
Exam move
Keep the Euler and Hamiltonian questions apart by writing the deciding test for each. Practise one tournament insertion, one bipartite colouring obstruction and one check of Ore's condition on a graph that fails Dirac's. When counting circuits, state whether start and direction are fixed before dividing.
For each graph you meet, try the obstructions first; if none applies, check Ore's condition before searching for a circuit by hand. Practise building circuits on graphs that satisfy Dirac's condition, so the construction step feels as routine as the check.
Working through Hamiltonian Paths and Circuits in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Hamiltonian Paths and Circuits question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.