3.4k 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.

retagged | 3.4k views

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
1why this is out-of-syllabus-now?
0

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

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