Home / Engineering / Design and Analysis of Algorithms / Question

M

Mr. Dubey • 51.62K Points
Coach

Q.) 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
Correct answer : Option (A) - number of vertices in u=number of vertices in v

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).

Share

Discusssion

Login to discuss.