A megoldáshoz ismételjük el a 16. feladatra adott bizonyítást, mert ebből fogunk továbblépni:
Ha van egy ember, aki legfeljebb n másikat ismer, akkor ez az n ember együttesen mindenki mást ismer. Ha viszont bármely ember legalább n+1 másikat ismer, válasszunk ki egy x embert. Ő ismer legalább n+1 embert. A maradó 2n–2 embert valahogyan párokba állítjuk, és bármely kettőnek van közös ismerőse, ez n–1 ember, ok x-szel az az n ember, akik együtt ismerik a többit. Ugyanez a gondolatmenet azt adja, hogy legfeljebb 4n2/3 ember is kiválasztható úgy, hogy azok együtt mindenkit ismerjenek. Elég bebizonyítani, hogy van 2n2/3 ember, akik együtt az összes többit ismerik, hiszen ezeknek egy-egy ismerősét hozzájuk véve együtt már mindenkit ismerni fognak. Hogy ne kelljen sokat egész részekkel számolni, csak azt az esetet mutatjuk be, amikor n köbszám.Ha van valaki, aki legfeljebb 2n2/3 embert ismer, akkor kész vagyunk: az ismerősei együtt mindenki mást ismernek, ez 2n2/3 ember. Ha viszont bármely ember több, mint 2n2/3 másikat ismer, akkor bárhogyan választunk ki n2/3 embert, van köztük n1/3, akiknek van közös ismerősük (hiszen együttesen – multiplicitással számolva – 2n4/3 ismerősük van, tehát legalább egy olyan ember van, aki legalább n1/3-szor ismétlődik). Ezt addig csinálhatjuk, amíg van legalább n2/3 ember, akiket még nem vettünk tekintetbe. Vagyis n– n2/3 embert n1/3-os csoportokba állíthatunk úgy, hogy egy-egy csoportnak legyen közös ismerőse, ez lényegében n2/3 ember, a maradó (kevesebb, mint) n2/3 embert pedig hozzávesszük, így (kevesebb, mint) 2n2/3 embert kapunk, akik együtt az összes többit ismerik. Ezzel a bizonyítást befejeztük.
A feladat folytatását lásd a II. fejezet 57. feladatában.Megmutatjuk, hogy cn1/2-nél kevesebbre nem igaz az állítás.
Vegyünk ugyanis egy m pontú teljes gráfot, Km-et és csináljunk ebből egy G gráfot a következő módon. A G gráf csúcsai legyenek az n pontú teljes gráf élei, ez n=m(m–1)/2 pont. A G gráfban két pontot akkor kötünk össze, ha a megfelelő éleknek Km-ben van közös csúcsuk. A G gráfban bármely két pontnak van közös szomszédja (és G minden pontja 2m–4-ed fokú, ami nagyságrendileg 2n1/2).Igaz a következő: akárhogyan választunk ki (m–1)/2-nél kevesebb élt a Km teljes gráfban, van olyan él, amellyel egyiknek sincs közös végpontja, vagyis az új gráfban akárhogyan választunk ki (m–1)/2-nél kevesebb pontot, van olyan pont, amellyel egyikük sincs összekötve. (m–1)/2 lényegében (n/2)1/2, biztos nagyobb, mint (n/2)1/2–1.