Existence Theorems for Hamiltonian Cycles¶

Basic Lemma¶

Consider a simple graph \(G\) with \(n\) vertices, which has two non-adjacent vertices \(a, b\) such that \(d_a + d_b \geq n\). Now consider graph \(H\), which is the same as graph \(G\) except that vertices \(a, b\) are connected by an edge. We claim that graph \(G\) has a Hamiltonian cycle if and only if graph \(H\) has a Hamiltonian cycle.

The first part of the proof is clear, because if \(G\) has a Hamiltonian cycle, \(H\) will also have that cycle. (No edge was removed.)

Now, to prove the second part, assume \(H\) has a Hamiltonian cycle. If this cycle does not use the edge \(ab\), then \(G\) also has the same cycle, and the claim is proven. So, assume this cycle uses the edge \(ab\). Consequently, there must exist a Hamiltonian path in \(G\) that starts at \(a\) and ends at \(b\).

Now, suppose our Hamiltonian path is \(a = v_1, v_2, ..., v_n = b\). If \(v_1\) has an edge to \(v_i\) and \(v_n\) has an edge to \(v_{i-1}\), then we can find a Hamiltonian cycle in graph \(G\). (Go directly from \(v_1\) to \(v_i\), then traverse the path from \(v_i\) to \(v_n\), then go directly from \(v_n\) to \(v_{i-1}\), then traverse the path from \(v_{i-1}\) to \(v_1\)).

Now, for every vertex \(v_i\) such that \(v_1\) has an edge to it, color \(v_{i-1}\) red. And for every vertex \(v_i\) such that \(v_n\) has an edge to it, color \(v_i\) blue. If we can prove that there exists a vertex that has been colored both red and blue, the problem will be solved. We know that by assumption \(d_a + d_b \geq n\), so the number of vertices we colored is at least \(n\). On the other hand, vertex \(v_n\) is never colored (why?). So we have \(n-1\) vertices that have been colored at least \(n\) times. Therefore, by the Pigeonhole Principle, there exists a vertex that has been colored twice. Thus, there exists a vertex that is both blue and red simultaneously, which implies that a Hamiltonian cycle exists in \(G\).

Other Theorems¶

Here we present a few theorems that you can easily prove using the basic lemma stated above.

• If, in graph \(G\), the degree of every vertex is at least \(\frac{n}{2}\), then a Hamiltonian cycle exists in this graph.

• If, in graph \(G\), for any two non-adjacent vertices \(a\) and \(b\), we have \(d_a + d_b \geq n\), then a Hamiltonian cycle exists in this graph.