A

Admin • 833K Points
Coach

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

Explanation by: Admin

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.

You must be Logged in to update hint/solution

Discusssion

Login to discuss.

Be the first to start discuss.