6,827 views

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.

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

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}$

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

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 )$??

Is this topic in syllabus ?

yes it is

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 )$.

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

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

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).
by