Complete bipartite graph

The complete bipartite graph $K_{r,s}$ has vertex classes of sizes $r$ and $s$ and contains all $rs$ edges between the classes.

If a bipartite graph with class sizes $m,N$ has at least $\beta mN$ edges, double count pairs consisting of an $s$-set in the first class and a common neighbour in the second. Convexity of binomial coefficients gives some $S$ with $|N(S)|\ge N\left(\genfrac{}{}{0ex}{}{\lfloor \beta m\rfloor }{s}\right)/\left(\genfrac{}{}{0ex}{}{m}{s}\right)$. When $s\le \beta m/2$, the quotient is at least $(\beta /2{)}^s$. This turns density into a large complete bipartite subgraph.

A star graph is the complete bipartite graph with one centre and $m$ leaves. Any pair of its edges meet at the centre.