A property of a graph is monotone if the whole graph has the property when a subgraph does.
A property of a graph is non-trivial if the empty graph does not have the property.
The study of the minimum size of a graph with a monotone, non-trivial property, or the maximum size of a graph without it.
If then has a path of length . If then is Hamiltonian.
Note that if then the degree condition implies that is connected.
Claim. has no cycle of length . Proof of claim. Suppose there is a cycle. Obviously if then is Hamiltonian, contradiction. If then there is a vertex not in the cycle. is connected, so we can find a path from the cycle to , giving a path longer than , contradiction.
In particular, . Now by hypothesis .
Let , . If then is a cycle of length . So .
Certainly and , so in fact .
If then we have a path of length , so a path of length .
If then we have a path of length , which is a contradiction because it must involve vertices. Therefore is Hamiltonian.
If then is Hamiltonian.
Let be a graph with vertices and no path of length . Then with equality iff is a union of copies of .
If then with equality iff .
Consider . If is disconnected apply induction to each component. Otherwise is connected and , or there would be a vertex that could be joined to a path traversing the to make a path of length .
By theorem 6.4 at least one has . By the induction hypothesis . Therefore .