(a) Consider the complete bipartite graph K_{m,n} with bipartition (X,Y) in which \lvert X \rvert=m and \lvert Y \rvert=n. The graph K_{m,n} has an edge between every vertex in X and every vertex in Y. The total number of pairs of vertices with one vertex in X and one vertex in Y is mn. Hence result follows.

(b) Let G be a simple bipartite graph on \nu vertices. W.l.o.g. let us say that one part has m vertices and thus the other part has \nu -m vertices. By part (a), G has at most m(\nu-m) edges.

Consider the following two cases:

Case 1: \nu is even.

Case 2: \nu is odd.

In Case 1, m(\nu-m) reaches its maximum which m=\frac{\nu}{2} (when the parts of the partition have an equal number of vertices). Thus \epsilon\leq m(\nu-m)\leq \frac{\nu}{2}(\nu-\frac{\nu}{2})=\frac{\nu^2}{4}.

In Case 2, m(\nu-m) reaches its maximum which m=\frac{\nu+1}{2} (when one of the parts of the partition have just one vertex more than the other part). Thus \epsilon\leq m(\nu-m)\leq \frac{\nu+1}{2}(\nu-\frac{\nu+1}{2})=\frac{\nu^2-1}{4}\leq\frac{\nu^2}{4}. \square