TITLE: Prove that if G has minimum cycle length 6, then its complement is Hamiltonian
QUESTION [0 upvotes]: I am trying to prove the following statement:
"If a graph $G$ is not a forest and its shortest cycle has length at least $6$, then its complement $\overline{G}$ is Hamiltonian."
I'm pretty sure my proof is either incorrect or has missing parts but here is what I could come up with:
First off, since $G$ is not a forest then $G$ contains at least one cycle, and we know it has length at least 6. 
By contrapositive, let's assume that $\overline{G}$ is not Hamiltonian and let us prove that there exists a cycle of length $<6$ in $G$. By Ore's theorem, there exists a pair of non-adjacent vertices $(u,v)$ in $\overline{G}$ such that $d(u) + d(v) < |G|=n$. This implies that:
$$d_G(u) + d_G(v) = (n - 1) - d_{\overline{G}}(u) + (n - 1) - d_{\overline{G}}(v) > 2n - 2 - n = n - 2 $$
Since $u$ and $v$ are non-adjacent in $\overline{G}$, they are in $G$. If we remove $e=(u,v)$ from $G$, then we still have that $d_G(u) + d_G(v) \geq n-3$. Now, if $u$ and $v$ have one common neighbour, then adding back $e$ creates a cycle of length $3$ and thus we're done. Otherwise $N(u)\cap N(v) = \emptyset$, and since $G\setminus\{u,v\}$ has $n-2$ vertices, then at most $1$ vertex $w$ is not in $N(u)\cup N(v)$. Recall that $G$ is not a forest, and thus contains at least one cycle $C$. Assume that $|C|\geq 6$, then at least $5$ vertices of $C$ are not $w$. Therefore, the following cycle exists and has length 4:
$$ c_1-c_2-u-v-c_1$$
where $c_1,c_2\neq w\in C $.

REPLY [0 votes]: It's important here to consider the possible $C$ that we could be given. While these cases are not too difficult, they are not quite covered by your example.

If $C$ contains neither $u$ nor $v$, then there are two points $c_1,c_2$ in $C$ connected to the same element of $\{u,v\}$, say $u$. Take the smaller path between these points in $C$, along with the two-edge path $c_1-u-c_2$, in order to obtain a cycle of length less than 6.
Say $C$ contains exactly one of $\{u,v\}$, say $u$. If $u$ is connected to at least 3 elements, then there are two such elements, say $c_1$ and $c_2$, which are connected by a path containing less than 4 edges but not containing $u$. This path, along with the two-edge path $c_1-u-c_2$, forms a cycle of length less than 6. Otherwise, there are at least two elements $c_1,c_2$ of $C$ other than $u$ which are connnected to $v$. We can take the shorter path in $C$ connecting them and add that to $c_1-v-c_2$ to get a cycle of length less than 6.
Say $C$ contains both $u$ and $v$. If $u$ and $v$ are not consecutive in $C$, then take a path from one to the other and replace it with the edge $(u,v)$. Otherwise, there is at least one vertex $c$ which is not adjacent to $u$ or $v$ in $C$, but is adjacent to one, say $u$ in $G$. Replace a path in $C$ from $u$ to $c$ not with the edge $u-c$, giving us a cycle of length less than 6.

The rest of this proof looks great!
{"set_name": "stack_exchange", "score": 0, "question_id": 3311688}