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 be a bipartite graph. Let be the set of vertices in with , where . Then the cardinality of the set of edges from to satisfies
We can generalize slightly: if is a constant such that , then
The first version can be recovered by setting , which is the average degree of a vertex in . From this point of view, the bound is only useful when is smaller than the average degree. In particular, if , where and is the average density of a vertex in , then
Proof: We may divide the vertices of into vertices with degree at least and vertices with degree less than : . Summing degrees over the vertices of yields
Since each vertex in has degree less than , we have
Since , we have
Rearranging yields the desired result.
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.