Prove that $G$ or $\bar G$ must be nonplanar if G has 11 vertices.

Question

The exact problem is the following: "Let G be a graph with 11 vertices. Prove that $G$ or $\bar G$ must be nonplanar.

I went to my professor to discuss the proof, but she said it didn't quite work, that something was "off" about it. The following is the proof I presented:

Let $G$ be a graph with 11 vertices. It is clear that $\lvert{E(G)}\rvert$+$\lvert{E(\bar G)}\rvert$=$\lvert{E(K_{11})}\rvert$=$55$.

Assume, for the sake of contradiction, that both $G$ and $\bar G$ are nonplanar. Then $$\lvert{E(G)}\rvert+\lvert{E(\bar G)}\rvert \le (3\lvert{V(G)}\rvert-6)+(3\lvert{V(\bar G)}\rvert-6)=54. \Rightarrow\Leftarrow$$ Therefore, either $G$ or $\bar G$ is nonplanar.

So, where exactly does this proof fail? Any tips on the aesthetics of the proof would also be greatly appreciated.

Answer 1

So the $K_{11}$ has $55$ edges. Now lets form $G$ with $27$ edges: As you already wrote for a triangulation we have $3 V(G) - 6 = 27$ edges. But for $\overline{G}$ we have 28 edges left. Thus there is one edge that will violate the planarity of the triangulation in $\overline{G}$.