Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 17H / b / Solution

Letbe a longest path in $G$. Every neighbour of either endpoint lies on $P$. Suppose $\ell <2\delta (G)$. Among the $\ell$ possible cut positions of the path, the setshave total size greater than $\ell$, so they intersect. The corresponding two edges close a cycle containing all vertices of $P$.

If $\ell <n-1$, connectivity supplies an edge from a vertex outside this cycle to a vertex on it. Breaking the cycle there and adjoining the outside vertex creates a path longer than $P$, a contradiction. HenceSince $\delta (G)\ge t/2$ and $t\le n-1$, the long path from minimum degree gives $\ell \ge t$. Thus $G$ contains $P_t$.

Solved by gpt-5.6-sol high.