# isomorphic planar graph with its complement

I need to demonstrate that there is a finite set of planar graphs with the property that the graph G is isomorphic with its complement graph.Can you give me some suggestions or hints ?Thank you

-

## 1 Answer

I apologize for posting the full answer. Somehow I missed that you only need hints. I'll leave the full answer below and give few hints here.

• Hint 1 How many edges does a self-complementary graph have?
• Hint 2 What are the implications of Euler formula for planar graphs?

Full Solution follows.

Let $G$ be a self-complementary graph of order $n.$ Then $G$ has $\frac{n(n+1)}{4} = \mathcal{O}(n^2)$ edges. But from Euler's formula, every planar graphs has $\mathcal{O}(n)$ edges. Hence there are only finitely many self-complementary planar graphs.

To be more precise, Euler's formula implies that for a planar graph $G$ of order $n \geq 3$ we have $$|E(G)| \leq 3n-6$$ hence if $G$ is self complementary we have $$\frac{n(n+1)}{4} \leq 3n-6$$ which implies $3 \leq n \leq 8.$ Hence a self-complementary planar graph may have at most 8 vertices.

As it appears there are only 14 such graphs and they can be seen in the attached figure!

-