The popularity lemma is simple lemma about refining the vertices of a bipartite graph by degree. Since it gives you a lower bound on the number of edges that remain after refining, it can be used to show that not too many edges are lost by refining.

Popularity Lemma: Let ${G(A,B)}$ be a bipartite graph. Let ${B'}$ be the set of vertices in ${B}$ with ${degree\geq\mu}$, where ${\mu\geq 0}$. Then the cardinality of the set of edges from ${A}$ to ${B'}$ satisfies

$\displaystyle |E(A,B')|\geq |E(A,B)|-\mu|B|.$

We can generalize slightly: if ${\rho}$ is a constant such that ${|E(A,B)|\geq\rho|B|}$, then

$\displaystyle |E(A,B')|\geq (\rho-\mu)|B|.$

The first version can be recovered by setting ${\rho =|E(A,B)|/|B|}$, which is the average degree of a vertex in ${B}$. From this point of view, the bound is only useful when ${\mu}$ is smaller than the average degree. In particular, if ${\mu=c\rho}$, where ${0 and ${\rho}$ is the average density of a vertex in ${B}$, then

$\displaystyle |E(A,B')|\geq (1-c)|E(A,B)|.$

Proof: We may divide the vertices of ${B}$ into vertices with degree at least ${\mu}$ and vertices with degree less than ${\mu}$: ${B=B'\cup B\backslash B'}$. Summing degrees over the vertices of ${B}$ yields

$\displaystyle |E(A,B)|=\sum_{b\in B}\deg(b)= |E(A,B')|+\sum_{b\in B\backslash B'}\deg(b).$

Since each vertex in ${B\backslash B'}$ has degree less than ${\mu}$, we have

$\displaystyle \sum_{b\in B\backslash B'}\deg(b)\leq \mu|B'|\leq \mu|B|.$

Since ${|E(A,B)|\geq\rho|B|}$, we have

$\displaystyle \rho|B|\leq |E(A,B')|+\mu|B|.$

Rearranging yields the desired result. $\Box$

Although I’m sure this is an old result, I first saw this lemma in Guth and Katz’s 2008 paper on the joints problem.