= Solution
Let
$$
P=v_0v_1\cdots v_\ell
$$
be a longest <path in a graph>[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 sets
$$
\{i:v_0v_i\in E(G)\},
\qquad
\{i:v_{i-1}v_\ell\in E(G)\}
$$
have 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. Hence
$$
\ell\geq\min(2\delta(G),n-1).
$$
Since $\delta(G)\geq t/2$ and $t\leq n-1$, the <long path from minimum degree> gives $\ell\geq t$. Thus $G$ contains $P_t$.
Back to article page
