Válasszunk ki a társaságból $\left(d+1\right)$ tagot úgy, hogy közülük semelyik kettő ne ismerje egymást. A megmaradó $\left(2n-d-1\right)$ ember ismeretségeinek a száma legfeljebb $d\cdot \left(2n-d-1\right)$, ez egyben az összes ismeretség felső korlátja is, hiszen nincsen olyan ismeretség, amelyiknek legalább egyik tagja ne az utóbbi csoportból volna. A számtani és mértani közép összefüggése alapján azonban ez a szorzat biztosan kisebb $\left(n-\frac{1}{2}\right){}^2$-nél ‐ (egyenlő nem lehet, mert $d$ egész szám); ‐ így $n^2$-nél még inkább.