I/25. feladat megoldása:

Mindenki legfeljebb két másikat nem ismer, három személy esetében legfeljebb hat olyan van, akit legalább egyikük nem ismer. 3+6=9, még marad egy valaki, aki mindhármukat ismeri.

Általánosítás: Vegyünk egy n tagú társaságot, azt akarjuk, hogy bármely k embernek legyen közös ismerőse, s ehhez olyan feltételt akarunk megadni, hogy bármelyikük legalább d másikat ismerjen. Az a kérdés, hogy mekkorára kell választanunk d-t. Ha mindenki legalább d másikat ismer, akkor legfeljebb n–d–1-et nem ismer. Ez k ember esetében k(n–d–1) ember. Ehhez jön még az a k ember, akinek a közös ismerősét keressük, ez összesen legfeljebb k(n–d) ember. Akkor van biztosan közös ismerősük, ha ez a szám kisebb n-nél, vagyis hak(n–d) < n,ahonnand > (k–1)n/k.Azt kaptuk, hogy ha egy n tagú társaságban mindenki több, mint (k-1)n/k másikat ismer, akkor bármely k embernek van közös ismerőse.

Gráfelméleti nyelven: Ha egy n pontú (egyszerű) gráfban minden pont foka nagyobb, mint (k–1)n/k, akkor bármely k ponthoz található olyan pont, amellyel mindegyik össze van kötve.