Question

The maximum number of edges in a bipartite graph on 14 vertices is ___________

(a) 56

(b) 14

(c) 49

(d) 87

This question was addressed to me by my college professor while I was bunking the class.

The doubt is from Bipartite Graphs in portion Graphs of Discrete Mathematics

Answer 1

Right choice is (c) 49

Easiest explanation: Maximum number of edges occur in a complete bipartite graph when every vertex has an edge to every opposite vertex in the graph. Number of edges in a complete bipartite graph is a*b, where a and b are no. of vertices on each side. This quantity is maximum when a = b i.e. when there are 7 vertices on each side. So answer is 7 * 7 = 49.