The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.10 Hamiltonian Paths and Circuits

- one subject, every graph, every model, every mark
6 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 10 of 11 · COMP2121

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.

In this chapter

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

Q [5 marks]. This practice weighting was set for revision and is not an official University marking scheme. In a tournament on four players the path a, b, c, d has each player beating the next. A fifth player e loses to a and b but beats c. Extend the path to include e.
Inserting a new player into a Hamiltonian path of a tournament.Inserting a new player into a Hamiltonian path of a tournament. The blue arrows are the existing path from v1 to v4; v5 loses to v2 but beats v3, so the dashed step from v2 to v3 is replaced by the two amber arrows through v5.v1v2v3v4v5v2 beats v5v5 beats v3old step v2 to v3 is replaced
Inserting a new player into a Hamiltonian path of a tournament. The blue arrows are the existing path from v1 to v4; v5 loses to v2 but beats v3, so the dashed step from v2 to v3 is replaced by the two amber arrows through v5.
  • 2Find the first player on the path that e beats.
  • 2Insert e just before that player.
  • 1Check every arc on the new path.
The first player that e beats is c, and the player before c is b, who beats e. Inserting e between them gives the path a, b, e, c, d. Each arc points forward: a beats b, b beats e, e beats c and c beats d, so all five players are covered.
Sia tip — If the new player beats the first player, put it at the front; if it beats nobody, put it at the end.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works