Question

What is the maximum number of edges in a bipartite graph on 14 vertices?

(a) 78

(b) 15

(c) 214

(d) 49

I have been asked this question during an online interview.

Question is from Bipartite Graphs topic in division Graphs of Discrete Mathematics

Answer 1

Right answer is (d) 49

To elaborate: By definition, the maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n^2.

Substituting n = 14, we get maximum number of edges in a bipartite graph on 14 vertices,= (1/4) x (14)^2

          = (1/4) x 14 x 14

          = 49

∴ Maximum number of edges in a bipartite graph on 14 vertices = 49.