We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, that $|R| < k< |L|$, and that $k$ is much larger than $|R|$.

What is the minimal size (*i.e.*, number of edges) of the maximal biclique^{1}?

^{1}maximal biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.

smallerthan $k$". Is that right? $\endgroup$ – Dan Cranston Aug 9 '17 at 21:27