1.

Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?(a) Number of vertices in U = Number of vertices in V(b) Sum of degrees of vertices in U = Sum of degrees of vertices in V(c) Number of vertices in U > Number of vertices in V(d) Nothing can be saidThe question was asked in a job interview.Enquiry is from Bipartite Graphs topic in section Bipartite Graphs of Data Structures & Algorithms II

Answer»

The correct answer is (b) Sum of degrees of vertices in U = Sum of degrees of vertices in V

Easiest explanation - We can prove this by INDUCTION. By adding one edge, the degree of vertices in U is EQUAL to 1 as well as in V. Let us assume that this is true for n-1 edges and ADD one more edge. Since the given edge ADDS exactly once to both U and V we can tell that this statement is true for all n vertices.


Discussion

No Comment Found

Related InterviewSolutions