25.2 Hamiltonian paths

The Hamiltonian path problem is this: in a graph we want to find a path which visits every vertex once.

Here is a statement of Dirac’s theorem. Let $G=(V,E)$ be a simple graph.

We restrict $G$ to be only those graphs with at least four vertices (i.e. $|V|>3$). If the smallest degree in $G$ is $\frac{n}{2}$ (where $n=|V|$), then $G$ contains a Hamiltonian cycle.

To prove this we will use the extreme principle; that when solving problems it is worthwhile to focus on the smallest or largest values in a problem. In our case, we will consider $P=(v_{1},...,v_{k})$, the longest path in $G$. There are a few useful properties about this path; a very valuable one is that because of the minimum degree we know that there must be at least $\frac{n}{2}+1$ nodes. This is because all neighbours of $v_{1}$ must be in the graph (otherwise $P$ would not be the longest path, as we could extend $P$ using the neighbours of $v_{1}$ not in $P$), and $v_{1}$ has degree $\frac{n}{2}$, i.e. at least that many neighbours, and it is also in the graph, so we must add one. Therefore, we know that

What else would be nice to know about $P$? Well currently we have a path, and we would really like a cycle! Here we can apply some wishful thinking for example, it would be nice if there was a node in the path directly connected to both $v_{1}$ and $v_{k}$. Sadly, this is not possible, and applying the tried and tested trick of considering some examples (this is a really important thing to do in mathematics – always consider some actual examples) helps us to disprove this, consider e.g. this graph for $|V|=4$ does not have the desired property

However, we can instead try the next-best thing; what about two nodes, e.g. some $j\in\mathbb{Z}$ such that $v_{j}$ is connected to $v_{k}$ and $v_{j+1}$ is connected to $v_{1}$. This is not an obvious thing to come up with, and some wishful (and creative) thinking is kind of required to realise that we can build a cycle (and more to prove that this cycle will include all the nodes) using this. The idea is this - our cycle will \saystart at $v_{j+1}$ and continue to $v_{k}$, from where we can continue to $v_{j}$, and from there to $v_{1}$ and then back to $v_{j}$ (don’t forget to whom $v_{j}$ and $v_{j+1}$ are connected!) We are also happy in the case where we can find a $j$ such that $v_{j}$ is connected to both.

It helps to consider the example graph above. In that case $j=2$ (the path goes along the main horizontal) and therefore we start at $v_{3}$ (labelled as $3$ on the graph because yours truly is not very good at writing LATEXcode), advance to $v_{4}$, from where we can go to $v_{2}$, from there to $v_{1}$ and from there we can return to $v_{3}$. I’ve drawn the cycle below (there are arrow tips, but they are very small, so you may have to zoom in).

So now that we have a conjecture (this is maybe possible to come up with by drawing lots of graphs and guessing), we should try to prove it. There are two things to prove

• •
  ​

  that we can build a cycle in the way described above

• •
  ​

  that this cycle encompasses all the nodes

To prove the first part we can use the pigeonhole principle. Let us consider the set $\{x:0\leq x\leq k-1\}$. We can then define the functions

and

Note that we use $i+1$ for $A$ and $i$ for $B$ because we are looking for values which are next to each other.

We then know that there are at least $\frac{n}{2}$ values of $i$ in $S$ for which $A(i)$ is true (and the same for $B(i)$)¹¹ 1 because the minimum connectivity of the graph is $\frac{n}{2}$, and all the neighbours of $v_{0}$ and $v_{k}$ are in $S$..

We would like to show that there must be some value of $i$ for which $A(i)=B(i)=1$ (i.e. $A,B$ are true for this value, so the edges to the start and end that we believe exist, as exposited above, can be proven to be real). Suppose not - then we know that for all $i$, that $A(i)\neq B(i)$. That is, we know that

(that is, the sets are disjoint because they share no $i$), and this means that we can just add their cardinalities together, giving

but this is absurd as this implies that there are more than the $n-1$ possible values of $i$ (recall how $S$ was defined). Therefore we can form a cycle from $P$.

Then, to prove that the cycle derived by $P$ contains all the nodes, suppose not. In this case we can make a bigger path by just attaching the node not in the cycle to the cycle created from $P$, which creates a