Question

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 said

The question was asked in a job interview.

Enquiry is from Bipartite Graphs topic in section Bipartite Graphs of Data Structures & Algorithms II

Answer 1

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.