GATE CSE 1990 | Question: 1-viii

Question

A graph which has the same number of edges as its complement must have number of vertices congruent to ________ or ________ modulo $4$.

Comments

answer should be 0, 1 (in no particular order) modulo 4

---

@codeitram Simple and to the point answer!!

Answer 1

It is the definition of self complementary graph..The definition of self complementary graph is :

It is a graph which is isomorphic to its complement.

By using invariant of isomorphism and property of edges of graph and its complement , we have :

1. No of edges of isomorphic graphs must be the same.
2. no of edge of a graph $+$ no of edges of complementary graph = No of edges in $K_{n}$ (complete graph), where n is the no of vertices in each of the 2 graphs which will be the same

 So we know no of edges in $K_{n}  =  \frac{n\left(n-1\right)}{2}.$

 So no of edges of each of the above $2$ graph (a graph and its complement)  $=  \frac{n\left(n-1\right)}{4}$

 So this means the number of vertices in each of the $2$ graphs should be of the form “$4x$” or “$4x+1$” for integral value of no. of edges which is necessary.

Hence, the required answer is $4x$ or $4x+1\ldots.$ So that on doing modulo we get 0 which is the definition of congruence.

Comments

Nice explanation! @Habib

Number of vertices(n)

n congruent to 4x (mod 4)

or

n congruent to 4x+1 (mod 4)

 

put x=0 then

n congruent to 0 (mod 4)

or

n congruent to 1 (mod 4)

like wise for any integer x it is true(also true for negative x).

Because a is congruent to b (mod n) iff (a-b) is multiple of n.

---

In best answer.. we are talking about edges

So no of edges of each of the above 2 graph (a graph and its complement)  =n(n−1)4

then how can we say about vertices ??

So this means the number of vertices in each of the 2 graphs should be of the form “4x" or “4x+1" for integral value of no of edges which is necessary. 

It is not given that they are trees or something so that we can assume a direct relationship..

(E = V-1 ) …??

 

---

@ASNR1010 
In a graph with $n$ vertices, #edges possible = $n\choose 2$ = $\frac{n(n-1)}{2}$, where $n$ is number of vertices

Given graph is isomorphic to it's complement, $\therefore$ number of edges in both the graphs are equal.

$\therefore$ #edges in a graph = $\frac{n(n-1)}{4}$

$\therefore$ either $n$ is divisible by $4$ or $n-1$ is divisible by 4.

Therefore either $n \cong 0$ MOD $4$ or $n \cong 1$ MOD $4$