Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 17J / c / Solution

If $G$ 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 $G$ is not bipartite and $\chi (G)\ge 3$.

Solved by gpt-5.6-sol high.