A calculus of the absurd

24.2.2 Dirac’s theorem

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

\begin{equation} k \geq \frac {n}{2} + 1. \end{equation}

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

(-tikz- diagram)

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 “start” 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 code), 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).

(-tikz- diagram)

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; we will consider the set \(S = \{x_1, ..., x_{k-1}\}\). Of the items in this set, we know that there must be at least \(\frac {n}{2}\) values of \(i\) such that \(\{x_i, x_k\} \in E\) and also \(\frac {n}{2}\) values of \(i\) such that \(\{x_{0}, x_{i+1}\} \in E\). Therefore we have \(\frac {n}{2}\) values of \(i\) and \(\frac {n}{2} + 1\) values, so two of our values will have to double up.