# Prove that if G — (V, E) is an arbitrary bipartite graph, then $|E| \leq |V|^2/4$ using induction [duplicate]

let $$n=\mid V\mid$$

base case: let $$n=0$$. Thus lemma becomes vacuously true since both bipartitions will contain the empty set thus not a bipartite graph.

Inductive step:

let $$k\in\mathbb{N}$$, assume $$P(k)$$ show P(k+1): $$\forall G=(V,E), k+1 = \mid V \mid\Rightarrow \mid E\mid\leq\frac{(\mid k+1\mid)^{2}}{4}$$, where G is bipartite

I'm having trouble the inductive step, here's my intuition of how I think I should approach. create a subproof to show max possible edges in bipartite graph is when both bipartitions of V has the same size. Then we can assume if a bipartite graph is complete then proposition is satisfied for case 1. I think for Case two, prove for when # of edges are less than the max?

## marked as duplicate by mrtaurho, Adrian Keister, Lee David Chung Lin, Sam T, blubApr 12 at 18:20

• not sure if i'm approaching this correctly but case 1 when $\mid E \mid = \mid V1\mid\cdot\mid V2\mid$, where V1 , V2 are the bipartitions of V. Case 2, when $\mid E \mid < \mid V1\mid\cdot\mid V2\mid$ – neet Apr 11 at 3:44
If for $$k+1$$ vertices $$|E| \geq \frac{(k+1)^2}{4} +1$$, remove a vertex with degree $$\leq \lfloor\frac{k + 1}{2}\rfloor$$ (why does such a vertex exist?) to get a graph with $$k$$ vertices and more than $$\frac{k^2}{4}$$ edges, which contradicts $$P(k)$$.