25.2 Hamiltonian paths

25.2.1 The Hamiltonian path problem

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

25.2.2 Dirac’s theorem

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

We restrict GG to be only those graphs with at least four vertices (i.e. |V|>3|V|>3). If the smallest degree in GG is n2\frac{n}{2} (where n=|V|n=|V|), then GG 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=(v1,,vk)P=(v_{1},...,v_{k}), the longest path in GG. 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 n2+1\frac{n}{2}+1 nodes. This is because all neighbours of v1v_{1} must be in the graph (otherwise PP would not be the longest path, as we could extend PP using the neighbours of v1v_{1} not in PP), and v1v_{1} has degree n2\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

kn2+1.k\geq\frac{n}{2}+1. (25.1)

What else would be nice to know about PP? 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 v1v_{1} and vkv_{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|V|=4 does not have the desired property


However, we can instead try the next-best thing; what about two nodes, e.g. some jj\in\mathbb{Z} such that vjv_{j} is connected to vkv_{k} and vj+1v_{j+1} is connected to v1v_{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 vj+1v_{j+1} and continue to vkv_{k}, from where we can continue to vjv_{j}, and from there to v1v_{1} and then back to vjv_{j} (don’t forget to whom vjv_{j} and vj+1v_{j+1} are connected!) We are also happy in the case where we can find a jj such that vjv_{j} is connected to both.

It helps to consider the example graph above. In that case j=2j=2 (the path goes along the main horizontal) and therefore we start at v3v_{3} (labelled as 33 on the graph because yours truly is not very good at writing code), advance to v4v_{4}, from where we can go to v2v_{2}, from there to v1v_{1} and from there we can return to v3v_{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:0xk1}\{x:0\leq x\leq k-1\}. We can then define the functions

A(i)={v0,vi+1}EA(i)=\{v_{0},v_{i+1}\}\in E (25.2)


B(i)={vi,vk}EB(i)=\{v_{i},v_{k}\}\in E (25.3)

Note that we use i+1i+1 for AA and ii for BB because we are looking for values which are next to each other.

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

We would like to show that there must be some value of ii for which A(i)=B(i)=1A(i)=B(i)=1 (i.e. A,BA,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 ii, that A(i)B(i)A(i)\neq B(i). That is, we know that

{i:A(i)=1}{i:B(i)=1}=∅︀\{i:A(i)=1\}\cap\{i:B(i)=1\}=\emptyset (25.4)

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

|{i:A(i)=1}{i:B(i)=1}|\displaystyle|\{i:A(i)=1\}\cap\{i:B(i)=1\}| =|{i:A(i)=1}|+|{i:B(i)=1}|\displaystyle=|\{i:A(i)=1\}|+|\{i:B(i)=1\}| (25.5)
n2+n2=n\displaystyle\geq\frac{n}{2}+\frac{n}{2}=n (25.6)

but this is absurd as this implies that there are more than the n1n-1 possible values of ii (recall how SS was defined). Therefore we can form a cycle from PP.

Then, to prove that the cycle derived by PP 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 PP, which creates a