Maximum number of edges in a bipartite graph

There is no need to use induction here. A bipartite graph is divided into two pieces, say of size $p$ and $q$, where $p+q=n$. Then the maximum number of edges is $pq$. Using calculus we can deduce that this product is maximal when $p=q$, in which case it is equal to $n^2/4$.

To show the product is maximal when $p=q$, set $q=n-p$. Then we are trying to maximize $f(p)=p(n-p)$ on $[0,n]$. We have $f'(p)=n-2p$, and this is zero when $p=n/2$. After checking the end points we conclude that the maximum is $n^2/4$ at $p=n/2$.

The sum of the degrees of vertices $x$ and $y$ is indeed less than or equal to $n$. One reason for this is that if a vertex $v$ is adjacent to $x$ it cannot be adjacent to $y$ since $y$ and $v$ would be in the same part.

---

I would like to share my proof, please tell me what you think of it: The bipartite graph on $n$ vertices with the most edges is clearly a complete bipartite graph, otherwise we could take that graph, add an edge and we would have a graph with more edges.

In a complete bipartite graph with parts of size $k,n-k$ the vertices in the part with $k$ vertices have order $n-k$ and the vertices in the part with $n-k$ vertices have order $k$. The sum of the degrees is then $2k(n-k)$, so by the handshaking lemma the number of edges is $k(n-k)$

Now write $k$ as $\frac{n}{2}-j$. Then $k(n-k)=(\frac{n}{2}-j)(\frac{n}{2}+j)=\frac{n^2}{4}-l^2\leq \frac{n^2}{4}$

Suppose $p,q$ are nonnegative integers with $p+q=n,$ and that $K_{p,q}$ has the maximum number of edges among all bipartite graphs with $n$ vertices.

If we move one vertex from the side with $p$ vertices to the side with $q$ vertices, we lose $q$ edges and gain $p-1$ new edges. Since the number of edges was already maximized, we must have $p-1\le q,$ that is, $p-q\le1.$ Symmetrically, we also have $q-p\le1,$ and so $|p-q|\le1.$

If $n$ is even, then from $p+q=n$ and $|p-q|\le1$ it follows that $p=q=\frac n2,$ and $pq=\frac{n^2}4=\left\lfloor\frac{n^2}4\right\rfloor.$

If $n$ is odd, then $\{p,q\}=\left\{\frac{n-1}2,\frac{n+1}2\right\},$ and $pq=\frac{n^2-1}4=\left\lfloor\frac{n^2}4\right\rfloor.$