Maximum number of edges in a bipartite graph: why $\lfloor n^2/4\rfloor$ is optimal

In an (undirected, simple) bipartite graph $G=(U\cup W,E)$, every edge joins a vertex in $U$ to a vertex in $W$. Suppose $|U|=a$, $|W|=b$ and $a+b=n$. Then the maximum possible number of edges is achieved by the complete bipartite graph $K_{a,b}$, which has $ab$ edges, so $|E|\le ab$. The product $ab$ is maximized (for fixed $a+b=n$) when the parts are as equal as possible, giving the sharp bound $|E|\le \left\lfloor\frac{n^2}{4}\right\rfloor.$ This implies the multiple-choice answer is (ii) $n^2/4$ (and more precisely, $\le\lfloor n^2/4\rfloor$; equality when the bipartition sizes are $\lfloor n/2\rfloor,\lceil n/2\rceil$). The extremal graph is $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$. 3

Key terms: bipartite graph , complete bipartite graph , partite sets , extremal graph.

Step (i) why $|E|\le \dfrac{n^2}{4}$ holds

Let $G$ be bipartite with parts $U$ and $W$, $|U|=a$, $|W|=b$, $a+b=n$. Each vertex in $U$ can connect to at most all $b$ vertices of $W$, so the total number of edges satisfies $|E| \le a\cdot b.$ Thus we reduce the problem to maximizing the product $ab$ subject to $a+b=n$.

A standard algebra step gives $ab=a(n-a)= -\left(a-\frac n2\right)^2+\frac{n^2}{4}\le \frac{n^2}{4}.$ So always $|E|\le n^2/4$. When $n$ is even, taking $a=b=n/2$ gives equality $|E|=n^2/4$ via $K_{n/2,n/2}$. When $n$ is odd, the maximum becomes $\lfloor n^2/4\rfloor$, still bounded by $n^2/4$. 3

Key terms: simple graph , edge count , inequality.