Question

A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).

(a) 6k, 6k-1

(b) 4k, 4k+1

(c) k, k+2

(d) 2k+1, k

I had been asked this question in examination.

I would like to ask this question from Isomorphism in Graphs in section Graphs of Discrete Mathematics

Answer 1

The correct answer is (c) k, k+2

To explain I would say: By using invariant of isomorphism and property of edges of graph and its complement, we have: a) number of edges of isomorphic graphs must be the same.

b) number of edge of a graph + number of edges of complementary graph = Number of edges in Kn(complete graph), where n is the number of vertices in each of the 2 graphs which will be the same. So we know number of edges in Kn =  n(n-1)/2. So number of edges of each of the above 2 graph(a graph and its complement)  =  n(n-1)/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 number of edges which is necessary. Hence the required answer is 4x or 4x+1 so that on doing modulo we get 0 which is the definition of congruence.