Week 12: Hamiltonian graphs

In this final week of classes, we continued our study of interesting spanning subgraphs of a given (simple, connected) graph \(G=(V,E)\).
  • In week 9, we looked spanning trees. That is connected acyclic graphs with vertex set \(V\)
  • in week 11, we looked at Euler cycles: cycles with edge set \(E\)
Today, we look at a natural variant of the Euler cycle:
A graph is Hamiltonian iff it contains a Hamilton cycle
Examples of Hamiltonian cycles include a cycle itself, and any graph with a larger edge set than a Hamiltonian one. This implies that \(K_n\) is Hamiltonian in particular as a second family of examples.
A nice counterexample was raised in class as two cliques that were joined at a single vertex \(v\). For such a graph, it seemed plausible that we wouldnt find a Hamilton cycle, but this had yet to be proved formally. To this end, we will first exhibit some necessary conditions for a graph to be Hamiltonian:
For a Hamiltonian graph and \(S\subset V\), we have \[c(G\setminus S)\le \vert S\vert\]
It suffices to note that since \(G\) is Hamiltonian, any component connects to a vertex \(v\) outside of it. This vertex must lie in \(S\) (since otherwise \(v\) cannot be connected to any other component). For each \(v\), we can find at least 1 such vertex. Moreover, they must all be different, since they lie on a Hamiltonian cycle.We found a choice of different vertices corresponding to the different components in \(G\setminus S\). Hence the result
Applying this (admittedly) technical result to the case where \(S=\{v\}\), we obtain:
A Hamiltonian graph is 2-connected (ie at leas two vertices need to be remove to disconect the graph)
This explains why joining to cliques at a single vertex yields a non-Hamiltonian graph.

After finding a(n) (easy) necessary condition, we then went on to search for sufficient conditions. And now come to the reason why we ketp the topic of Hamiltonian graphs until the end. There simply isn't a nice TONCAS answer to the problem of Hamiltonian cycle (compare with planarity, Euler, bipartite, etc..) Here the sufficiency conditions are simply less intuitive and as a result, I just stated the relevant theorems without proof:
(Dirac) Assume that the degree of each vertex satisfies \[d(v)\ge \frac{\vert V \vert}{2}\] Then \(G\) is Hamiltonian
One can ask whether this bound \(\frac{(\vert V\vert}{2} \) is as tight as possible? The answer is yes: for any \(n=\vert V\vert \) there exists a non-Hamiltonian graph such that \(d(v)\le \frac{n}{2}-1\). (see the assigment)