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

Answer: 36

Explanation: If a bipartite graph has parts of sizes a and b with a + b = 12, the number of edges is at most a·b (every vertex in one part can connect to every vertex in the other).

• Maximize a·b subject to a + b = 12. Substitute b = 12 − a to get f(a) = a(12 − a) = 12a − a².

• The quadratic 12a − a² is maximized when a = 6 (vertex of the parabola), so take a = 6 and b = 6.

• Thus the maximum number of edges is 6 · 6 = 36.

Therefore, the maximum number of edges in a bipartite graph on 12 vertices is 36.