Show that if a graph G = (V,E) is bipartite, then it has at most n^2/4 edges if n is even, and at most (n^2 − 1)/4 edges if n is odd. Here n = |V| is the number of vertices in G.
I want to prove this using induction. The basis step would be to just inspect the graphs with 1 and 2 vertices and see that the theorem holds. I don't know where to go from here, any help would be appreciated.
First show that the conclusion is equivalent to the assertion that $G$ has at most $\left\lfloor\frac{n^2}4\right\rfloor$ edges.
Suppose that the result is true for bipartite graphs with fewer than $n$ vertices, and let $G$ be a bipartite graph with $n$ vertices. Let $U$ and $V$ be the parts of $G$, where $|U|\le|V|$; then $|U|\le\left\lfloor\frac{n}2\right\rfloor$. Remove one vertex from $V$, along with all of the edges incident at that vertex; the resulting graph $G'$ is bipartite on $n-1$ vertices, so by the induction hypothesis it has at most $\left\lfloor\frac{(n-1)^2}4\right\rfloor$ edges. We removed at most $\left\lfloor\frac{n}2\right\rfloor$ edges from $G$ to get $G'$, so $G$ has at most
$$\left\lfloor\frac{(n-1)^2}4\right\rfloor+\left\lfloor\frac{n}2\right\rfloor$$
edges. To complete the induction step, show that
$$\left\lfloor\frac{(n-1)^2}4\right\rfloor+\left\lfloor\frac{n}2\right\rfloor\le\left\lfloor\frac{n^2}4\right\rfloor\,.$$
If you’re interested, you can also show that the upper bound of $\left\lfloor\frac{n^2}4\right\rfloor$ edges is achieved in the complete bipartite graph $K_{\left\lfloor\frac{n}2\right\rfloor,\left\lceil\frac{n}2\right\rceil}$.