Math 240 Discrete Mathematics - Hamiltonian Graph

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

If (v_1) or (v_k) has a neighbour not on (p) then we can find a longer path, contradictor. If all neighbours of (v_1\dots v_k) are on the path. Look for (1\leq i\leq k) s.t. (\{v_i,v_k\}\in E), $\{v_i,v_{i+1}\} \in E::

  • ————-<——-<————-

    |                                 | 
    

    v_1—-<—v_i v_i+1———>————v_k | | ——–>———

let (S) be the set of neighbours of (v_k) on (P). Then for all (v_i \in S), we want to avoid an edge (\{v_i,v_{i+1}\}). Trying to avoid (|S|) edges. This leaves (k-1-|S|) possibilities. But (k<n) and (|S|\geq {n} \over {2}) so only have $< {n}\over{2} $ choices remaining. Thus there is (i) s.t. (\{v_1,v_{i+1}\},\{v_k,v_i\} \in E)

Then (v_1,v_2,\dots,v_i,v_k,v_{k-1},\dots,v_{i+1},v_1) is a cycle using the same vertices as (P). Then Observation 2 implies there is a path with (k+1) vertices, contradicting maximality of (k).

Proof of Theorem

By Lemma there is a Hamiltonian Path.

If for all (i) s.t. (\{v_n,v_i\}\in E) $\{v_n,v_{i+1}\}\notin E $ Then there are at most (n-1-\deg (v_n)) neighbours of (v_1) but (n-1-\deg (v_n) \leq n-1 - n/2 < n/2). This completes the proof.