# Hamiltonian Graph

## Theorem

(G(V,E)) with (n) vertices, (G) is Hamiltonian if (n\geq3) and each vertex has degree $\geq{ n \over 2}$

## Proof

First find a Hamiltonian path. Next, find a way to turn a Hamiltonian path into a Hamiltonian cycle.

Easy fact: In a graph with min degree k, there is a path with least k+1 vertices. To see this,

Note: on any path with (\leq k) vertices, every vertex of the path has a neighbour not on the path.

Observation: If (C) is a cycle of (k) vertices and some vertex (v) of the cycle has a neighbour (w) not on the cycle, then there is a path of length (k+1)

.. figure:: |filename|/math240res/images/hamiltonianexample2.png

Observation: If (G) has min degree $\geq {n \over {2}\}$, then (G) is connected. (G=(V,E)), $|R| \leq {n \over {2}\}$. Vertices in R have $\leq {|R| -1}$ neighbours.

## Lemma

If (G) has (n\geq 4) vertices, and (G) has min deg (\geq {\{n}\over {2}\}) then (G) has a Hamiltonian path.

## Proof

Let (v_1,v_2,\dots,v_k) be a maximum length path. Suppose (for a contracdiction) that (k<n)

P = (v_1 v_2 v_3 \dots v_i v_{i+1} \dots v_k) P is path