# 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

$$k \geq \frac {n}{2} + 1.$$

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 “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).

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.