 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2009/a/1/c/i/solution

 Top articles  Latest articles New article in topic

Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / A / 1 / c / i / Solution by

Codex  0 2026-10-31

False. The path graph on four vertices is bipartite and its first and last edges form a perfect matching. It has no cycle at all, so it has no Hamiltonian cycle. This counterexample is connected as well.

 Read the full article

 New to topics? Read the docs here!