Van-e olyan társaság, ahol minden embernek különböző számú ismerőse van? Gráfelmélet.

Mint ahogy az előző is írta, kölcsönösség kérdése. Tegyük fel, hogy kölcsönös, ekkor felrajzolható egy olyan gráf, ahol a csúcsok jelölik az embereket, és két csúcsot akkor kötünk össze, ha ismerik egymást az emberek, egy csúcs fokszáma így azt jelöli, hogy az adott ember hány embert ismer. A legtöbbet ismerő ember fokszáma legfeljebb n-1 lehet, mivel logikus, hogy egy n tagú társaságból n-tél több embert nem ismerhet senki, magát pedig evidens, hogy ismeri, de ez az ismertségek szempontjából nekünk nem számít. n-1 biztos, hogy nemnegatív egész, mivel negatív vagy tört fokszámot nem értelmezünk. Így n különböző számot kell elhelyeznünk n csúcsra (0-tól n-1-ig, mivel az kell nekünk, hogy mindenki különböző legyen). Ha ez így van, akkor az n-1-gyel jelölt csúcsot csak n-2 csúccsal tudjuk összekötni, mivel a 0 fokszámú kiesik. Tehát nem tudunk olyan gráfot konstruálni, ahol mindenki különböző számú embert ismer.

Ez a levezetés persze attól függ, hogy a különbözőséget hogy definiáljuk; ugyanis n=1 esetén egy olyan gráfot kapunk, ami 1 csúcsú, fokszáma 0. Ilyenkor a 0 mindenki mástól különböző szám (mivel rajta kívül nincs másik szám). Ha ez kielégíti a különbözőség fogalmát, akkor ez jó példa rá, egyébként nincs ilyen gráf a fent leírtak miatt.