Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ii/paper-2/17f/iv/solution
Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 2 17F iv Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-14
No. In the six-cycle with cyclic vertices , every edge belongs to one of the two alternating perfect matchings. However, the disjoint edges and cannot belong to a common perfect matching: the remaining vertices are not adjacent. Taking and gives the required bipartite graph counterexample.
New to topics? Read the docs here!