Hamiltonian Cycle

NOTE

A Hamiltonian cycle (or Hamilton cycle) in a graph is a simple cycle that visits every vertex exactly once and returns to the start.

Theorem: Dirac (1952)

NOTE

Every Graph $G=(V,E)$ with $|V|\ge 3$ and minimal degree $\delta (G)\ge \frac{|V|}{2}$ has a Hamiltonian cycle

Proof Structure:

1. The graph is connected
2. Induction:
   • For $k<n$: $k$-cycle (with $k$ vertices) $⟹$ There exists a $k+1$ long path
   • There is $k$ long path $⟹$ There exists $k+1$ long path or $k$-cycle

Proof:

1. Choose any $u,v\in V$
   • If $\{u,v\}\in E$ then $u,v$ are connected
   • Otherwise, $|N(u)|+|N(v)|+2=1+\frac{n}{2}+1+\frac{n}{2}=2+n⟹|N(u)\cap N(v)|\ge 2$ (by Siebformel) $⟹N(u)\cap N(v)\ne \varnothing$ $⟹$ There is a path between $u,v$

• $N(u)$ is the neighbors of vertex $u$
• $|N(u)|\ge \frac{n}{2}$ because $\delta (G)>\frac{n}{2}$
  • $⟹$ The graph is connected

2. Induction part:
   1. straightforward from the conclusion that $G$ is connected. We can always find a node that is connected to the cycle
   2. Assume there is a $k$ path
3. Case: $N(v_1)⊈\{v_2,\dots ,v_k\}$ or $N(v_k)⊈\{v_2\dots v_k\}$

• There is a node $u$ that is not yet in the path, so we can add node $u$ to the path

2. Case: $N(v_1)\subseteq \{v_2\dots v_k\}$ and $N(v_k)\subseteq \{v_2\dots v_k\}$

• Define $N^{+}(v_k)=\{v_{i+1}:v_i\in N(v_k)\}$
• $|N(v_1)\cap N^{+}(v_k)|>1$
• There exists $v_i$ such that $(v_1,v_i),(v_{i-1},v_k)\in E$

Application: Rotary Encoder

There are $k$ light emitters and light detectors. We want to arrange the holes on the plate in a certain way such that they encode $2^k$ directions. For $k=2$, we want to have 00, 01, 10, 11. However, we also want the codes of any two neighboring directions to differ in only one bit, because the light detectors are much more precise than the positions of the holes.

We can model this problem as finding a Hamiltonian cycle on a $k$ dimensional hypercube.

Solving this problem is straightforward. Suppose we have a Hamiltonian cycle on $k-1$ dimensional hypercube. We first break it into a Hamiltonian path, then duplicate the hypercube along the $k$-th dimension and finally connect the two paths together to form a new cycle.

How it looks like:

How to decide if a graph has a Hamiltonian cycle (effizient)

• Brute Force: $O(n!)\approx n^n\approx 2^{n\log n}$
• DP: $O(2^n)$, actually ~$n^2{2}^n$ time and ~$n\cdot 2^n$ memory

Consider a super computer with $10^{25}$ FLOPs ($10^7$ EFLOPs)

• Using brute force we can solve graph with ~25 nodes
• Using DP we can solve graph with ~84 node