Diracs theorem hamiltonian circuit example

Theorem

Let $G$ be a connectedsimple graph with $n$ vertices such that $n > 3$.

Ore's theorem proof

Let the degree of each vertex be at least $\dfrac n 2$.

Then $G$ is Hamiltonian.

Proof 1

Let $P = p_1 p_2 \ldots p_k$ be the longest path in $G$.

If $p_1$ is adjacent to some vertex $v$ not in $P$, then the path $v p_1 p_2 \ldots p_k$ would be longer than $P$, contradicting the choice of $P$.

The same argument can be made for $p_k$.

Ore's theorem

So both $p_1$ and $p_k$ are adjacent only to vertices in $P$.

Since $\map \deg {p_1} \ge \dfrac n 2$ and $p_1$ cannot be adjacent to itself, $k \ge \dfrac n 2 + 1$.

Claim

There is some value of $j \in \set {1, 2, \ldots, k}$ such that:

$p_j$ is adjacent to $p_k$

and:

$p_{j + 1}$ is adjacent to $p_1$.

Aiming for a contradiction, suppose that the claim is not true.

Then since all verticesadjacent to $p_1$ or $p_k$ lie on $P$, there must be at least $\map \deg {p_1}$ vertices on $P$ not adjacent to $p_k$.

Since all th