Q.

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
Answer» B. sum of degrees of vertices in u = sum of degrees of vertices in v
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.
1.3k
0
Do you find this helpful?
8

View all MCQs in

Design and Analysis of Algorithms

Discussion

No comments yet

Related MCQs