Question

A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?

(a) Number of vertices in U=Number of vertices in V

(b) Number of vertices in U not equal to number of vertices in V

(c) Number of vertices in U always greater than the number of vertices in V

(d) Nothing can be said

The question was posed to me in unit test.

Question is from Bipartite Graphs topic in portion Bipartite Graphs of Data Structures & Algorithms II

Answer 1

Right choice is (a) Number of vertices in U=Number of vertices in V

Easiest explanation - We know that in a bipartite graph sum of degrees of vertices in U=sum of degrees of vertices in V. Given that the graph is a k-regular bipartite graph, we have k*(number of vertices in U)=k*(number of vertices in V).