*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 .