in Graph Theory retagged by
6,827 views
26 votes
26 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.
in Graph Theory retagged by
6.8k views

2 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

 

1
1
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
0
0

5 Answers

56 votes
56 votes
Best answer
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 Comments

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

Can Someone explain this part---- "Since n\left ( n-1 \right ) must be divisible by 4, it follows that n=0 or 1 \left (\mod 4 \right )??

0
0
Is this topic in syllabus ?
0
0

yes it is

0
0
17 votes
17 votes

By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., n\frac{\left ( n-1 \right )}{4} edges for a self-complementary graph on n vertices. Since n\left ( n-1 \right ) must be divisible by 4, it follows that n=0 or 1 \left (\mod 4 \right ).


Answer: D. Congruent to 0 \left (\mod 4 \right ), or, 1 \left (\mod 4 \right ).


Source: Self-Complementary Graph -- from Wolfram MathWorld

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

2 Comments

ok ans is D ,   but what option A  means ?   ie  A multiple of 4 ?
3
3
Because multiple of 4 does not suffice the condition of 4K + 1
1
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