Past exam of the short options course of the University of Oxford / 2014 / 6 / a

A Hamilton cycle is a cycle visiting every vertex of a finite graph exactly once before returning to its starting point. A Hamilton path is a path visiting every vertex exactly once, with no requirement to return or to have its endpoints adjacent. Both conditions concern visiting vertices, rather than traversing every edge.

Let $v_1\dots v_k$ be a longest path in the finite simple graph. Every neighbor of either endpoint lies on this path, since an outside neighbor would extend it. Define two subsets of $\{1,\dots ,k-1\}$:Their sizes are $d(v_1)$ and $d(v_k)$. The degree hypothesis gives $|I|+|J|\ge n\ge k$, but there are only $k-1$ possible indices. Hence some $i$ belongs to both. The edges at that index close a cycle through every vertex of the path:The graph is connected: any component has at least $n/2+1$ vertices by the minimum degree, so two components would exceed $n$ vertices. If $k<n$, connectedness gives an edge from this cycle to an outside vertex. Starting at that vertex and traversing the cycle without its closing edge gives a path with $k+1$ vertices, a contradiction.

Thus $k=n$ and the cycle is a Hamilton cycle, proving Dirac's theorem. The overlap-of-indices argument is why the degree threshold is half the number of vertices.

Take the complete bipartite graph $\boxed{K_{3,4}}$. Its seven vertices have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.

Every cycle in a bipartite graph alternates between its two parts, using equal numbers of vertices from each. A Hamilton cycle here would have to use three vertices from one part and four from the other, which is impossible. Thus three-vertex connectivity and minimum degree three do not suffice for Hamiltonicity in this seven-vertex example.