Question

A graph G is self-complementary if G is isomorphic to the complement of G.

suppose G is a self complementary graph with n vertices. How many edges must G have? Why?

Answer 1

Since,we know that for a graph to be isomorphic to another graph, the no of edges in both graph needs to be same.

Let E(G) = edges in graph G & E(G') = no of edges in complement of graph G.

Total number of edges = E(G) + E(G') = n(n-1)/2

In self- complementary graph , E(G) = E(G')

So,E(G) + E(G') = E(G) + E(G) = 2E(G) = n(n-1)/2

E(G) = n(n-1)/4.

Hence, An n-vertex self-complementary graph has exactly half no of edges of the complete graph.

Now,for the number of edges to be integer, n(n-1) must be divisible by 4.so, n must be congruent to (0 mod 4) or (1 mod 4), for instance,a 6-vertex graph cannot be self-complementary.