Define the complement $\bar{G}$ of a graph as follows: $V(\bar{G})=V(G)$ and for all $x,y \in E(\bar{G})$ if and only if $x,y \notin E(G)$. Suppose that $G$ is a graph that is not a forest and does not contain cycles of length $4$ or lower. Use Ore's theorem to show that $ \bar{G}$ contains a Hamilton cycle.
Ore's Theorem: If $G$ is a graph with $ n \geq 3$ and $ d(x)+d(y) \geq n$ for all pairs $x \neq y$ nonadjacent vertices,then G is Hamiltonian.
I've started this question by supposing there exists $x,y \in V(\bar{G})$ that satisfies $d_\bar{G}(x)+d_\bar{G}(y) \leq n-1$ for all $x \neq y$ nonadjacent vertices. I've also noted that $d_G(x)+d_\bar{G}(x)+d=n-1$ since it just forms the complete graph. I was told to show that $G[N_G(x) \cup N_G(y)]$ (where $N_G(-)$ are the neighbours of $x$/$y$) is a tree on $n-1$ vertices, but I'm unsure how to go about doing this. Any help would be appreciated
This is awkward because you cannot prove (it's not always true) that $\overline G$ satisfies the requirements of Ore's theorem, so you have to deal with the case where it doesn't separately.
Suppose $x$ and $y$ are non-adjacent in $\overline G$, so they are adjacent in $G$. Write $N(x), N(y)$ for the vertices adjacent (in $G$) to $x$ and $y$ respectively. Note that $d_{\overline G}(x)=n-1-|N(x)|$, etc.
Now because there are no cycles of length $3$, $N(x)\cap N(y)=\varnothing$. Also, there are no edges within $N(x)$ or $N(y)$ for the same reason. Because there are no cycles of length $4$, there are no edges between $N(x)$ and $N(y)$ either (apart from the edge $xy$). This means there are no cycles within $N(x)\cup N(y)$. Since $G$ is not a tree, there must be at least one other vertex, so $|N(x)|+|N(y)|\leq n-1$. If there are two such vertices, we get $|N(x)|+|N(y)|\leq n-2$ and we are done.
If there is only one vertex $z$ not in $N(x)\cup N(y)$ then a Hamilton cycle in $\overline G$ can be constructed by starting at $x$, going through vertices in $N(y)$ in turn, then going through vertices in $N(x)$ ending at $y$, then going to $z$ and back to $x$.