retagged by
12,761 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

Best answer
59 votes
59 votes
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}$
edited by
4 votes
4 votes
Ans: D
because for self complimentary graphs, no. of vertices should be of the form 4k or 4k+1
0 votes
0 votes

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:

Related questions

5 votes
5 votes
1 answer
1
Vikrant Singh asked Feb 1, 2015
853 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,315 views
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.