Let $G$ be a simple graph with at least $11$ vertices. Prove that either $G$ or its complement $\overline{G}$ must be nonplanar. Connectivity?

1.8k Views Asked by At

I have seen many solutions to this problem and understand all of them, but I keep thinking they are over simplified because the connectivity of $\overline{G}$ is not addressed.

Solutions in general assume that $G$ is planar, and then we know that $e_G \leq 3(|V| -2) $ holds ($e_G$ is the edge set of $G$, number of vertices of $G$ is $n$). Then from the complete graph on $n$ vertices we know that $e_{\overline{G}} = \frac{1}{2} n (n-1) - e_G$. If we then assume that $\overline{G}$ is planar, then sub in the fact that $e_{\overline{G}} \leq 3(|V|-2)$ to get a contradiction. This is where I don't understand why connectivity is not considered. I know it is possible to have a connected graph that has a disconnected complement, and the inequality $e_{\overline{G}} \leq 3(|V|-2)$ only holds if $\overline{G}$ is connected (or so my lecture notes from class say), so don't we need to consider a case where $\overline{G}$ is disconnected? And if so how would I approach such a case?

Any help is much appreciated. Thanks!