Extra material : Day 7

Theorem (Dirac) Let G be a simple graph on n vertices in which every vertex has degree at least n/2. Then G has a Hamilton cycle.

Proof : Let G be a counterexample with the largest possible number of edges - we shall derive the contradiction that G contains a Hamilton cycle after all. By maximality of |E(G)|, if x and y are any two non-adjacent vertices in G, then addition of the edge {x, y} would create a Hamilton cycle in G. In other words, there must exist a path from x to y in G passing through all the vertices. Denote the path as

y = x_{1} → x_{2} → ⋯ → x_{n−1} → x_{n} = z.

We consider two sets S and T, defined as follows :

S = {i : 1 ≤ i ≤ n − 1 and {y, x_{i+1}} ∈ E(G)},
T = {i : 1 ≤ i ≤ n − 1 and {x_{i}, z} ∈ E(G)}.

On the one hand, both S and T are subsets of {1, ..., n − 1}, so

|S ∪ T | ≤ n − 1.  (1)

On the other hand,

|S| = deg(y) ≥ n/2,
|T | = deg(z) ≥ n/2,

which implies that

|S| + |T | ≥ n.  (2)

From (1) and (2), we can deduce that S ∩ T is non-empty. Let i ∈ S ∩ T. Then the following is a Hamilton cycle in G :

y → x_{2} → ⋯ x_{i} → z → x_{n−1} → ⋯ → x_{i+1} → y.

With that, the proof of the theorem is complete.