Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 17I (Graph Theory)

Letbe a longest path. Every neighbour of either endpoint lies on $P$. Among the $m-1$ possible cuts between consecutive vertices, mark a cut $i$ when $v_m{v}_i$ is an edge and also mark it when $v_1{v}_{i+1}$ is an edge. There are at leastmarks, so some cut receives both marks. The path edges together with $v_m{v}_i$ and $v_{i+1}{v}_1$ form a cycle through all vertices of $P$.

The degree assumption makes $G$ connected: two components would each contain at least $n/2+1$ vertices. If $m<n$, connectedness gives an edge from a vertex outside the cycle to a vertex on it; breaking the cycle there produces a path with $m+1$ vertices, contrary to maximality. Hence $m=n$, so $G$ is Hamiltonian. This proves the Dirac theorem in this case.

Let $P=v_0\dots v_{\ell }$ be a longest path. All neighbours of $v_0$ lie on $P$, in the colour class opposite to $v_0$, so $\ell \ge 2k-1$. If $\ell \ge 2k$, the first $2k$ edges give the required path. Otherwise $\ell =2k-1$, and all $k$ vertices of the opposite colour on $P$ must be neighbours of $v_0$; in particular $v_0{v}_{\ell }$ is an edge, giving a cycle of length $2k$. The graph $K_{k,k}$ has minimum degree $k$ but only $2k$ vertices, so it has no path of length $2k$.

For the stronger assertion, assume there is no $4$-cycle. Rotate a longest path about each edge from $v_0$ to obtain $k$ possible endpoints in the colour class of $v_0$. Every neighbour of each rotated endpoint lies on $P$, since otherwise the corresponding path could be extended. In a $4$-cycle-free bipartite graph, two vertices in one colour class have at most one common neighbour. The neighbourhood bound for a square-free bipartite graph therefore shows that the colour class opposite to $v_0$ contains at least $2k-1$ vertices of $P$. If the endpoints have opposite colours, repeating the argument from $v_{\ell }$ gives the same bound for the other class. If they have the same colour, their class has one more vertex on $P$ than the opposite class. In either case $P$ has at least $4k-2$ vertices and length at least $4k-3$. Consequently $G$ contains either such a path or a $4$-cycle.