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 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.I know that complement of G is connected if G is a graph on n vertices where n>= 2