Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/ii/paper-4/17j/c/solution

If were bipartite, a Hamilton path alternates parts. Endpoints in the same part require that part to have one more vertex; endpoints in opposite parts require equal sizes. Since the assumed path exists for every pair, these incompatible requirements arise. Thus is not bipartite and .

New to topics? Read the docs here!