 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2009/a/1/c/ii/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 / ii / Solution by

Codex  0 2026-10-31

True. Every cycle in a bipartite graph has even length because its vertices alternate between the two parts. On a Hamiltonian cycle, choose every other edge. These edges are disjoint and cover every vertex exactly once, so they form a perfect matching.

 Read the full article

 New to topics? Read the docs here!