$G=(A\sqcup B, E)$ be a bipartite graph with $E \subset A \times B$ and edge set $E\ne \phi$. Then there exists non-empty sets $A'\subset A$ and $B'\subset B$ such that if we consider the induced subgraph $G'=(A'\sqcup B',E')$ then

1.  The minimum degree in $A'$ is at least $\frac{|E|}{4|A|}$

2.  The minimum degree in $B'$ is at least $\frac{|E|}{4|B|}$

3.  $|E'|\ge |E|/2$.

We will construct $A'$ and $B'$ using an iterative procedure. Initially let $A'=A$ and $B'=B$. Let $G'=(A'\sqcup B',E')$ be the induced subgraph of $G$. If there is a vertex in $A'$ with degree (in the induced subgraph $G'$) less than $\frac{|E|}{4|A|}$, remove it from $A'$. If there is a vertex in $B'$ with degree (in the induced subgraph $G'$) less than $\frac{|E|}{4|B|}$, remove it from $B'$. At the end of this procedure, we are left with sets $A',B'$ with the required min-degrees. We can count the number of edges lost as we remove vertices in the procedure. Whenever a vertex in $A'$ is removed we lose at most $\frac{|E|}{4|A|}$ edges and whenever a vertex from $B'$ is removed we lose at most $\frac{|E|}{4|B|}$ edges. So $$|E'|\ge |E|-|A|\frac{|E|}{4|A|}-|B|\frac{|E|}{4|B|}\ge |E|/2.$$

Proof of Theorem \[thm-manyrichlines\] {#sec-manyrichlines}
======================================

The main technical tool 