retagged by
12,785 views
28 votes
28 votes

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

  1. A multiple of 4
  2. Even
  3. Odd
  4. Congruent to 0 $mod$ 4, or, 1 $mod$ 4.
retagged by

6 Answers

0 votes
0 votes

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

0 votes
0 votes

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.

Answer:

Related questions

5 votes
5 votes
1 answer
1
Vikrant Singh asked Feb 1, 2015
856 views
How many labelled sub-graphs of $K_n$ are isomorphic to $W_{n-1}$?(Where $K_n$ : Complete graph with $n$ vertices , $W_n$ : Wheel graph with $ n+1$ vertices)1.$\frac{(n-1...
42 votes
42 votes
6 answers
4
go_editor asked Sep 28, 2014
17,332 views
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.