# Helly’s theorem

Suppose ${A}_{1},\mathrm{\dots},{A}_{m}\subset {\mathbb{R}}^{d}$ is a family of convex sets, and every $d+1$ of them have a non-empty intersection^{}. Then ${\bigcap}_{i=1}^{m}{A}_{i}$ is non-empty.

###### Proof.

The proof is by induction^{} on $m$. If $m=d+1$, then the statement is vacuous^{}. Suppose the statement is true if $m$ is replaced by $m-1$. The sets ${B}_{j}={\bigcap}_{i\ne j}{A}_{i}$ are non-empty by inductive hypothesis. Pick a point ${p}_{j}$ from each of ${B}_{j}$. By Radon’s lemma, there is a partition of $p$’s into two sets ${P}_{1}$ and ${P}_{2}$ such that $I=(\mathrm{conv}{P}_{1})\cap (\mathrm{conv}{P}_{2})\ne \mathrm{\varnothing}$. For every ${A}_{j}$ either every point in ${P}_{1}$ belongs to ${A}_{j}$ or every point in ${P}_{2}$ belongs to ${A}_{j}$. Hence $I\subseteq {A}_{j}$ for every $j$.
∎