GATE CS 2014 Set 2 Q3 — Graphs: Connectivity, Matching, Colouring

A bipartite graph $G = (V, E)$ is a graph whose vertices can be divided into two disjoint and independent sets $V_1$ and $V_2$ such that every edge connects a vertex in $V_1$ to one in $V_2$.

Let the number of vertices in $V_1$ be $n_1$ and in $V_2$ be $n_2$. We are given the total number of vertices:

The maximum number of edges in a bipartite graph with partitions of size $n_1$ and $n_2$ occurs when the graph is a complete bipartite graph $K_{n_1, n_2}$. The number of edges in $K_{n_1, n_2}$ is given by:

To maximize the product $n_1 \times n_2$ subject to the constraint $n_1 + n_2 = 12$, the two parts should be as equal in size as possible:

Therefore, the maximum number of edges is: