Thread: graph theory question

Prove that if n = 12 and G is a simple graph on n vertices, then it is not possible for both G and the complement of G to be planar.

I know that:
for a graph to be non planar we have to either find a subgraph isomorphic to k5 or k3,3 or a subdivision of k5 or k3,3

and I know that complement of G is connected if G is a graph on n vertices where n>= 2

but I'm not sure if I'm on the right track and how exactly to combine these ideas to come up with a solid proof.

This Wikipedia article gives a necessary condition for a graph to be planar: where is the number of edges. If is the number of edges in the complement graph, then is the number of edges in . It seems to me that this necessary condition cannot hold for both graphs.

That this condition is necessary can apparently be proved using Euler's formula (in the same article).

I know that complement of G is connected if G is a graph on n vertices where n>= 2

I am not sure about this: what if G consists of two connected points? Then its complement is two isolated points, i.e., not connected. Connectedness has to be taken care of because both Euler's formula and the condition above are true for connected graphs.