A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
A. 100
B. 140
C. 80
D. 20
A. 100
B. 140
C. 80
D. 20
Correct choice is A. 100
Let the given bipartition X have x vertices, then Y will have 20-x vertices. We need to maximize x*(20-x). This will be maxed when x=10.