Az I/10. feladat megoldása:

Tegyük fel, hogy van ötven ember, akik közül senki nem ismeri a másikat. Ültessük le őket egy kerek asztal mellé és mutassuk be egymásnak azokat, akik egymás mellett ülnek, valamint mutassuk be egymásnak az egymással szemben ülőket: az elsőt a 26.-nak, a másodikat a 27.-nek, és általában az i-ediket a 25+i-ediknek. Ekkor minden embernek pontosan három ismerőse lesz. Az első kérdésre tehát igen a válasz. Hasonlóan okoskodhatunk száz tagú társaság esetén és általában bármilyen páros tagú társaság esetén. Tegyük fel, hogy van 2n ember, akik közül senki nem ismer senkit. Leültetjük őket egy kerek asztal köré, ismét bemutatjuk egymásnak az egymás mellett ülőket és az egymással szemben ülőket. (Most két ember akkor ül egymással szemben, ha a sorszámuk között pontosan n a különbség.) Így kapunk egy olyan 2n tagú társaságot, ahol minden ember három másikat ismer. (Az ábra n=4-re, azaz nyolctagú társaságra mutatja a konstrukciót.)

Ha viszont 51 (99, vagy általában páratlan sok: 2n+1) tagja van a társaságnak, akkor nem lehetséges, hogy mindenki pontosan három másik embert ismerjen. Számoljuk ugyanis össze, hány ismeretség lenne ez esetben. Mindenki három másikat ismer, ez 51·3 (99·3, (2n+1)·3), viszont így minden ismeretséget kétszer számolunk, hiszen az ismeretség „mindkét résztvevőjénél” megszámoltuk. Vagyis az ismeretségek száma 51·3/2 (99·3/2, (2n+1)·3/2), ami nem egész szám, s ez lehetetlen.

Ha a kapott állítást átfogalmazzuk gráfelméleti nyelvre, azt kapjuk, hogy páros n-re van n pontú gráf, amelyben minden pont foka három, páratlan n-re nincs.

DEFINÍCIÓ: Azokat a gráfokat, amelyekben minden pont foka azonos, reguláris gráfnak nevezzük. Ha minden pont foka d, akkor a gráf d-reguláris.
Ezek szerint előző megállapításunk így is fogalmazható:

Ha n páros, akkor van n pontú 3-reguláris gráf, ha n páratlan, akkor nincs.

A feladat folytatása: I/19

Tovább