Show $\overline{G}$ is Hamiltonian

Question

Let $G$ be a graph that is not a forest with a shortest cycle of length of at least 5. Prove that $\overline{G}$ is Hamiltonian.

proofs involving showing something is Hamiltonian are giving me a hard time as there is no Theorem that gives a necessary and sufficient condition for a graph to be Hamiltonian (or at least from what i've learned). If someone could provide a hint to get me started in the right direction it would be greatly appreciated, Thanks!

Answer 1

The best idea is to apply some sufficient condition. Ore's theorem is a good option.

EDIT. Let $|G| = n$. Suppose $\deg_{\overline{G}}v_1 + \deg_{\overline{G}}v_2 < n$ for vertices $v_1$ and $v_2$ that are not adjacent in $\overline{G}$. Then $\deg_{\overline{G}}v_1 + \deg_{\overline{G}}v_2 \le n - 1$ therefore $\deg_{G}v_1 + \deg_{G}v_2 \ge n - 1$ and $v_1$ and $v_2$ are adjacent in $G.$ If these veritces share a common neighbour in $G$ then there is a cycle of length $3$ that is forbidden. Thus there are $n - 3$ vertices $v_3, v_4, \ldots, v_{n - 1}$ each of which is adjacent to either $v_1$ or $v_2$, but not to both of them. Also these $n - 3$ are pairwise non-adjacent for the sake of no cycle of length $3$ or $4$. But there should be at least one cycle. Therefore the last vertex $v_n$ is adjacent to $v_i$ for $3 \le i < n$ that is adjacent to $v_1$ and $v_j$ for $3 \le j < n$ that is adjacent to $v_2$ and no more vertices to avoid cycles of length $3$ or $4$ again. So $G$ is a cycle of length $5$ with all other vertices being adjacent to either $v_1$ or $v_2$ that are adjacent vertices of this cycle. Since $v_3, v_4, \ldots, v_{n - 1}$ are pairwise non-adjacent in $G$ then thes are pairwise adjacent in $\overline{G}$. So $\overline{G}$ has a cycle $v_1, v_j, v_3, v_4, \ldots, v_{\min\{i, j\} - 1}, v_{\min\{i, j\} + 1}, \ldots, v_{\max\{i, j\} - 1}, v_{\max\{i, j\} + 1}, \ldots, v_{n - 1}, v_i, v_2, v_n, v_1$ and therefore is Hamiltonian.

And if $\deg_{\overline{G}}v_1 + \deg_{\overline{G}}v_2 \ge n$ for any vertices $v_1$ and $v_2$ that are not adjacent in $\overline{G}$ we can apply Ore's theorem.

P. S. Sorry for the complete solution, but you didn't catch my hint.

Answer 2

We can solve this problem by a variant on the proof of Dirac's theorem (which is a great proof to know, because variants on it come up a lot). The proof of Dirac's theorem goes like this:

1. The graph $\overline G$ is connected.
2. If we can find a path of length $k$ in $\overline G$, we can either extend it to a path of length $k+1$ or get a cycle of length $k$.
3. If we can find a cycle of length $k$ in $\overline G$, either $k=n$ (and we have the Hamiltonian cycle we wanted) or we can extend it to a path of length $k+1$. (This uses 1.)

I can give more hints if you have trouble proving any of the three statements above in this setting.