GATE CSE 2015 Set 2 | Question: 28

Question

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is

• A. A multiple of 4
• B. Even
• C. Odd
• D. Congruent to 0 $mod$ 4, or, 1 $mod$ 4.

Comments

An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3.[1] Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

 

wikipedia

 

---

n(n-1)/4 means either n is divisible by 4 or (n-1) is divisible by 4

If n is divisible by 4 means
n = 0 mod 4

If (n-1) is divisble by 4 means
(n-1) = 0 mod 4
n = 1 mod 4

Answer 1

Since graph is isomorphic to its complement thus, 

edges in G + edges in G’ = edges in complete graph 

E+E= edges in complete graph  (since both graphs are same hence no of edges is also same)

2E= n(n-1)/2                                      (max number of edges in graph)

4E= n(n-1)     ---------(i)

now such combination possible is only for 

n=4       as    4(3)= 4(3)       from above equation (i)

n=5       as    4(5)= 4(5)       from above equation (i)

hence option D is the best answer

Answer 2

An n-vertex self-complementary graph has exactly half number of edges of the complete graph i.e.

n(n-1) / 4  edges.

Since n(n-1) must be divisible by 4, n must be congruent to 0 mod 4 or 1 mod 4.