3 Eulerian and Hamiltonian cycles 3.1 Euler’s theorem and König’s theorem on bi-partite graphs 4 Spanning Trees

3.2 Hamiltonian cycles

The Hamilton cycle is a cycle passing through every vertex exactly once.

Theorem 3.9.

(Dirac, 1952) If $G$ is a graph on $n$ vertices with $n\geq 3$ and $\delta(G)\geq n/2$ , then $G$ contains an Hamilton cycle.

Example 3.10.

For $n$ odd, consider the complete bi-partite graph $K_{(n-1)/2,(n+1)/2}$ . The minimum degree is $(n-1)/2$ and the graph does not have a Hamiltonian cycle. Why ?

Exercise(A) 3.11.

For $n$ odd, consider the graph $G_{1}$ formed by attaching two copies of $K_{(n+1)/2}$ at a single vertex. What is the minimum degree and does the graph have a Hamiltonian cycle ? Modify the construction for $n$ even suitably.

Proof.

Suppose $G$ is a counterexample to the theorem and $G$ be such a graph with maximal number of edges i.e., addition of an edge to $G$ creates a cycle. Let $v\nsim w$ and hence $G\cup(v,w)$ will contain a Hamilton cycle $v=v_{1}v_{2}\ldots v_{n}=w,v$ . Thus $v_{1}v_{2}\ldots v_{n}$ is a simple path. Define sets $S_{v}\coloneqq\{i:v\sim v_{i+1}\}$ and $S_{w}\coloneqq\{i:w\sim v_{i}\}$ . Since $\delta(G)\geq n/2$ , $|S_{v}|,|S_{w}|\geq n/2$ and further $S_{v},S_{w}\subset\{1,\ldots,n-1\}$ . Hence $S_{v}\cap S_{w}\neq\emptyset$ and assume that $i_{0}\in S_{v}\cap S_{w}$ . Then $v=v_{1}v_{2}\ldots v_{i_{0}}w=v_{n}v_{n-1}\ldots v_{i_{0}+1}v_{1}=v$ is a Hamiltonian circuit in $G$ , contradicting our assumption. ∎

A straightforward modification of the above proof gives the following more general result.

Theorem 3.12.

(Ore, 1960) If $G$ is a graph on $n$ vertices such that $d_{u}+d_{v}\geq n$ for all $u\nsim v$ , then $G$ is Hamiltonian.

We will now see a necessary condition for a graph to be Hamiltonian. For a subset $S\subset V$ , we denote $G-S$ as the graph obtained by removing all the vertices in $S$ and edges incident to those vertices. From our results on $\beta_{0}(G)$ , we know that $G-S$ has at most $|S|+1$ components for $S\subset E$ and $G$ connected.

Exercise 3.13.

Is there a bound for $\beta_{0}(G-S)$ for $G$ connected and $S\subset V$ ?

Theorem 3.14.

Suppose $G$ is Hamiltonian. Then $G-S$ has at most $S$ connected components for any $S\subset V$ .

Exercise 3.15 (Counterexample to necessity condition).

Show the following graph provides a counterexample to the above theorem.

Figure 3.1: Counterexample to necessity condition for Hamiltonian cycles

Proof.

Let $C_{1},\ldots,C_{K}$ be the components of $G-S$ . Assume we start our Hamilton cycle at $v_{1}\in C_{1}$ . ∎

Corollary 3.16.

Suppose $G$ is bi-partite and Hamiltonian. Then $|V_{1}|=|V_{2}|$ where $V_{i}$ are the partitions.

Proof.

From previous theorem, the number of components of $G-V_{1}$ (which is $|V_{2}|$ ) is at most $|V_{1}|$ and so $|V_{2}|\leq|V_{1}|$ . By symmetry, we get the other inequality. ∎