Question

A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?

(a) n

(b) n/2

(c) n/4

(d) data insufficient

The question was posed to me in an online quiz.

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

Answer 1

Correct option is (b) n/2

To explain: We can prove this by calculus. Let x be the total number of vertices on set X. Therefore set Y will have n-x. We have to maximize x*(n-x). This is true when x=n/2.