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 be a simple graph.
We restrict to be only those graphs with at least four vertices (i.e. ). If the smallest degree in is (where ), then 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 , the longest path in . 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 nodes. This is because all neighbours of must be in the graph (otherwise would not be the longest path, as we could extend using the neighbours of not in ), and has degree , 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 ? 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 and . 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 does not have the desired property
However, we can instead try the next-best thing; what about two nodes, e.g. some such that is connected to and is connected to . 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 and continue to , from where we can continue to , and from there to and then back to (don’t forget to whom and are connected!) We are also happy in the case where we can find a such that is connected to both.
It helps to consider the example graph above. In that case (the path goes along the main horizontal) and therefore we start at (labelled as on the graph because yours truly is not very good at writing LATEXcode), advance to , from where we can go to , from there to and from there we can return to . 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 . We can then define the functions
Note that we use for and for because we are looking for values which are next to each other.
We then know that there are at least values of in for which is true (and the same for )11 1 because the minimum connectivity of the graph is , and all the neighbours of and are in ..
We would like to show that there must be some value of for which (i.e. 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 , that . That is, we know that
(that is, the sets are disjoint because they share no ), 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 possible values of (recall how was defined). Therefore we can form a cycle from .
Then, to prove that the cycle derived by 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 , which creates a