McqMate
| 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. | |
View all MCQs in
Design and Analysis of AlgorithmsNo comments yet