2.8k 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 | 2.8k 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}$
by Boss (13.5k points)
edited by
+2
1why this is out-of-syllabus-now?

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

by Active (1.6k points)
Ans: D
because for self complimentary graphs, no. of vertices should be of the form 4k or 4k+1
by (57 points)
+3
ok ans is D ,   but what option A  means ?   ie  A multiple of 4 ?
0
Because multiple of 4 does not suffice the condition of 4K + 1