1.

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, kI 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»

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.


Discussion

No Comment Found

Related InterviewSolutions