57.          a) Az I/16-ban alkalmazott megoldás nyomán haladunk. Válasszunk ki egy tetszőleges embert: ő és az ismerősei együtt mindenkit ismernek (most őrá is szükség van, mert akiket ismer, azokkal nem biztos, hogy van közös ismerőse). Ha tehát van a társaságnak olyan tagja, aki legfeljebb n-et ismer, akkor kész vagyunk.

Tegyük fel, hogy mindenkinek legalább n+1 ismerőse van. Most is kiválaszthatunk találomra valakit, az ő legalább n+1 ismerősével akkor már nincs gondunk. Marad még 2n–2 ember, ezeket kellene párba állítanunk úgy, hogy bármely párnak legyen közös ismerőse. Ha e 2n–2 ember között van kettő, akik nem ismeri egymást, akkor nekik van közös ismerősük, K₁, válasszuk ki K₁-et és hagyjuk el e két embert. A maradó 2n–4 ember közül megint keresünk kettőt, akik nem ismerik egymást, s megismételjük az eljárást, kiválasztjuk egy közös ismerősüket, K₂-t. Addig választunk ki K_i embereket, amíg el nem akadunk. Az eljárás csak akkor akad el, ha néhány lépés után a maradó 2l ember között már nincs kettő, akik ne ismernék egymást, vagyis e 2l ember közül már mindenki mindenkit ismer. De akkor bármelyiküket kiválaszthatjuk, s ő már ismerni fogja a többit. Így tehát mindenképpen találunk legfeljebb n–1 további embert, akik együtt a maradék 2n–2-őt ismerik. Ebben az esetben tehát találtunk n embert, akik együtt mindenkit ismernek.

b) Könnyen ellenőrízhető, hogy amikor az I. fejezet 26. feladatánál azt bizonyítottuk, hogy mindig van 4n^2/3 olyan ember, akik együtt mindenkit ismernek, valójában csak azt használtuk, hogy az ismeretség-gráf 2-átmérőjű.