Prove that for a bipartite graph $G$ on $n$ vertices the number of edges in $G$ is at most $\frac{n^2}{4}$.
I used induction on $n$.
Induction hypothesis: Suppose for a bipartite graph with less than $n$ vertices the result holds true.
Now take a bipartite graph on $n$ vertices.Let $x,y$ be two vertices in $G$ where an edge exist between $x$ and $y$. Now remove these two vertices from $G$ and consider this graph $G'$. $G'$ has at most ${(n-2)^2}\over4$. Add these two vertices back. Then the number of edges $G$ can have is at most
$$|E(G')|+d(x)+d(y)-1$$
My question is in my proof I took $d(x) + d(y) \le n$, where $d(x)$ denotes the degree of vertex $x$. Can I consider $d(x)+d(y) \leq n$? I thought the maximum number of edges is obtained at the situation $K_{\frac n 2,\frac n 2}$
Best Answer
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$.