= De Bruijn--Erdos pair-covering inequality
{c}
If $r_x$ denotes the number of lines through $x$ in a nontrivial finite linear space on $v$ points, then
$$
\sum_x\binom{r_x}{2}\geq\binom v2.
$$
To prove it, let $k_L$ be the line sizes. The inequalities $k_L\leq r_x$ whenever $x\notin L$, counted at each integer threshold, give
$$
\sum_x(r_x-t)_+\geq\sum_L(k_L-t)_+
$$
for every $t\geq1$. Summing in $t$ and using $\binom s2=\sum_{t\geq1}(s-t)_+$ gives
$$
\sum_x\binom{r_x}{2}\geq\sum_L\binom{k_L}{2}=\binom v2,
$$
where the last identity counts pairs of points by their unique line.
Back to article page
