The Gateway to Computer Science Excellence
+18 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 by
retagged by | 3.4k views

3 Answers

+49 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
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 )??

+15 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
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,503 answers
95,331 users