# Extremal graph theory

Definition 6..1 (Monotone)

A property of a graph is monotone if the whole graph has the property when a subgraph does.

Definition 6..2 (Non-trival property)

A property of a graph is non-trivial if the empty graph does not have the property.

Definition 6..3 (Extremal problem)

The study of the minimum size of a graph with a monotone, non-trivial property, or the maximum size of a graph without it.

Theorem 6..4 (Condition for a graph to be Hamiltonian)   Let be a connected graph of order . Suppose that for every pair of non-adjacent vertices , .

If then has a path of length . If then is Hamiltonian.

Note that if then the degree condition implies that is connected.

Proof. Suppose that is not Hamiltonian. Let be a path of maximal length.

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.

Corollary 6..5 (G.A. Dirac)

If then is Hamiltonian.

Theorem 6..6

Let be a graph with vertices and no path of length . Then with equality iff is a union of copies of .

Proof. By induction on .

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 .

Subsections
John Fremlin 2010-02-17