The Greatest Number of Edges on a Bipartite Graph Let $G$ be a bipartite graph on $p$ vertices. Find a formula in terms of $p$ that determines the greatest number of edges that $G$ could have. Prove that this formula is correct.
Let $V$ be the set of vertices for $G$. Then $\lvert V \rvert = p$.
Let $M$ be the set of vertices of group one for $G$.
Let $N$ be the set of vertices of group two for $G$.
The maximum number of edges that $G$ can have is:
$$\lvert M\rvert \lvert N\rvert$$
Implying that every vertex in group one is adjacent to every vertex in group two.
Imagine $\lvert M\rvert$ and $\lvert N \rvert$ as sides of a rectangle. Then such a rectangle would have a perimeter equal to $2p$, and an area of $\lvert M\rvert \lvert N\rvert$.
Using the perimeter to solve for $\lvert N \rvert = p - \lvert M\rvert$. Sub this value into the formula for Area and take the derivative to maximize the area of the rectangle:
$$\frac{dA}{d\lvert M\rvert} = p-2\lvert M \rvert$$
$$\frac{p}{2} = \vert M \rvert$$
Note that $N \cup M = V$, and so $\lvert M \rvert + \lvert N \rvert = p$
Subbing in $\frac{p}{2}$ for $\lvert M \rvert$, it is revealed that $\lvert N \rvert = \lvert M \rvert$.
Therefore the formula for the greatest number of edges on a bipartite graph on $p$ edges is $\frac{p^2}{4}$. $\blacksquare$
Is this a valid proof? Any advice would be appreciated!
 A: Everything looks good except for when $p$ is odd, the part where you say it has at most $MN$ edges if the parts have sizes $M$ and $N$ is very good.
I would proceed as follows:
Clearly $M+N=p$ so we can assume $M\geq N$ and  $M=\frac{p+k}{2}$ and $N=\frac{p-k}{2}$, for some non-negative integer $k$. The options for $k$ are $0,2,\dots,p$ if $p$ is even and $1,3,\dots p$ when $p$ is odd.
Notice that the number of edges is then $\frac{p^2-k^2}{4}$. So this is maximized when $k=1$ if $p$ is odd and when $k=0$ when $p$ is even. So the final answer is $\frac{p^2}{4}$ when $p$ is even and $\frac{p^2-1}{4}$ when $p$ is odd.
A: As was pointed out in the comments, the use of continuous techniques like differentiation when dealing with a discrete problem like this is a little suspect.  While it is often a good heuristic, turning it into a proper proof can sometimes be a bit tedious.
Carry on Smiling's answer is a great way of answer this problem while staying within the discrete domain.  I'll show another general technique below, since it can often be useful in such situations - it's a discrete version of the variational technique.
Very often these discrete optimisation problems are solved by taking the variables to be as equal as possible - this is true, for example, when you are maximising a convex function with the sum of your variables fixed.  For example, here we have two variables, $M$ and $N$, with the function $MN$ to be maximised and the constraint $M + N = p$.
Without loss of generality, we may assume $M \ge N$.  We wish to show that $M$ and $N$ should be as equal as possible.  For contradiction, suppose $M - N \ge 2$.  Consider decreasing $M$ by $1$ and increasing $N$ by $1$; that is, set $M' = M - 1$ and $N' = N+1$.  Then $M' + N' = M - 1 + N + 1 = p$, and
$$ M' N' = (M - 1)(N + 1) = MN - N + M - 1 = MN + (M - N - 1) > MN, $$
since $M \ge N + 2$.
Hence if $(M,N)$ is optimal, they must be as equal as possible, so $M = \left\lceil \frac{p}{2} \right\rceil$ and $N = \left\lfloor \frac{p}{2} \right\rfloor$.
One can also run this argument at the graph level - consider the complete bipartite graph with parts of size $M$ and $N$, and if $M \ge N + 2$, move one vertex from the larger part to the smaller part, and count what happens to the number of edges.
While this may not seem that useful, consider the more general problem of determining the maximum number of edges in a $k$-partite graph on $p$ vertices.  Writing out the exact form of the maximum is a pain, but this variational argument goes through pretty easily.  I'll leave the details as an exercise for the reader. ;-)
