Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 17J (Graph Theory)

This is Dirac theorem. Take a longest path $v_1\dots v_k$. All neighbours of its ends lie on it. If no index $i$ has both $v_1{v}_{i+1}$ and $v_k{v}_i$, the two end-neighbour sets have total size at most $k-1$, contradicting $2\delta \ge n\ge k$. Such an index closes a cycle through the path, and maximality plus connectedness makes it Hamiltonian. For even $n$, the disjoint union of two copies of $K_{n/2}$ has minimum degree $n/2-1$ and is not Hamiltonian. For odd $n$, $K_{(n-1)/2,(n+1)/2}$ has minimum degree $(n-1)/2$ and no Hamilton cycle because its bipartition sizes differ.

Deleting $s$ vertices from a Hamilton cycle leaves at most $s$ path components, so the property is necessary. It is not sufficient: the Petersen graph is 1-tough, meaning $c(G-S)\le |S|$ for every separating set $S$, but it is not Hamiltonian.

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$.