The Gateway to Computer Science Excellence
+15 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 Veteran (105k points)
retagged by | 2.8k views

3 Answers

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

by Active (1.6k points)
+3 votes
Ans: D
because for self complimentary graphs, no. of vertices should be of the form 4k or 4k+1
by (57 points)
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
50,647 questions
56,479 answers
100,554 users