How can I construct a graph $G$ of order $8$ such that $G$ is connected but $\overline{G}$ isn't? Also, is it possible for me to construct it in such a way that neither $G$ nor $\overline{G}$ are planar?
Is there some sort of standard construction algorithm or a clever way I can do this? Or am I just supposed to do trial and error? I don't see a clear solution right away.
On
Let the vertices of $G$ be $1,2,3,\dots,8$. Let $1,2,$ and $3$ be isolated, and all the other vertices be adjacent to one another, so that $G$ has a subgraph isomorphic to $K_5$.
In $\overline{G}$ each of $1,2$ and $3$ is adjacent to each of $4,5,$ and $6$, so $\overline{G}$ has a subgraph isomorphic to $K_{3,3}$.
Neither $G$ nor $\overline{G}$ is planar. $\overline{G}$ is connected, but $G$ is not. It is easy to modify this example so that both $G$ and $\overline{G}$ are connected and nonplanar. I'll leave that to you.
Hint If $G$ is connected but has very few edges then $\bar{G}$ will have too many edges to be planar.
What is the smallest possible connected graph of order 8?