Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

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!

enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.