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

---

complement of a graph can be found by subtacting the edges from Kn with edges in orignal graph.

no of edges in a complete graph with n vertices = n(n-1) / 2

thus, edges in graph + edges in complement of that graph = n(n-1) / 2

 now as the graph is self-complementary, so edges in graph = edges in complement of that graph

hence, edges = n(n-1)/4

 

---

@gatecse why is this out of syllabus now?

---

@TanayH mujhe nhi pta 

---

either n is divisible by 4 or n-1 is divisible by 4 thats why the  last option D will be correct . here 0 mod 4  this is for n and 1 mod 4 is for (n-1)

Answer 1

Ans D

$E(G) + E(G') = \frac{n(n-1)}{2}$, where $E(G)$ denotes the no. of edges in $G$. ($G + G'$ will be a complete graph)

for self complementary graphs, $E(G) = E(G')$

$E(G) = \frac{n(n-1)}{4}$

Comments

1why this is out-of-syllabus-now?

---

Can Someone explain this part---- "Since  must be divisible by , it follows that  or ??

---

Is this topic in syllabus ?

---

yes it is

Answer 2

By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e.,  edges for a self-complementary graph on  vertices. Since  must be divisible by , it follows that  or .

---

Answer: D. Congruent to , or, .

---

Source: Self-Complementary Graph -- from Wolfram MathWorld

Answer 3

Ans: D
because for self complimentary graphs, no. of vertices should be of the form 4k or 4k+1

Comments

ok ans is D ,   but what option A  means ?   ie  A multiple of 4 ?

---

Because multiple of 4 does not suffice the condition of 4K + 1

Answer 4

This question can be answered without any knowledge of formulas too by considering two examples as below :

1. A cycle of size 5 which become a star like graph again resulting in the same. 
2. A graph with 4 vertices {1, 2, 3, 4}and edges (1, 2) and (3, 4).

Answer 5

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 6

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.