The maximum number of edges in a bipartite graph on 12 vertices is ______.

GATE 2014 · Discrete Mathematics · Graph Connectivity · medium

Answer: 36

1. Apply max-edges bipartite formula: v = 12. Max edges = floor(12^2 / 4) = floor(144 / 4) = 36.
2. Verify with K_{6,6}: K_{6,6} has 6 * 6 = 36 edges. Any other split like K_{5,7} gives 5*7 = 35 < 36. So the maximum is 36.