Feladat:	B.4592	Korcsoport: 16-17	Nehézségi fok: átlagos
Füzet:	2014/május, 287. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Gráfelmélet, Konstruktív megoldási módszer
Hivatkozás(ok):	Feladatok: 2014/január: B.4592

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. Az ismeretségi rendszert szemléltessük egy irányítatlan gráffal, ahol az emberek a csúcsok, és két csúcs pontosan akkor van összekötve éllel, ha a nekik megfeleltetett emberek ismerik egymást. Így a feladat feltétele szerint minden csúcs fokszáma 3. Minden gráfban a csúcsok fokszámainak összege páros, ezért a csoport létszáma csak páros lehet. Bármely két ember vagy ismeri egymást, vagy van közös ismerősük. Tehát ha kiválasztunk valakit, akkor annak 3 ismerőse van, és ennek a 3 ismerősnek van fejenként még 2 másik ismerőse (akik egymástól nem feltétlenül különböznek). Ez legfeljebb $1+3+6=10$ főt jelent. Tehát a létszám nem lehet más, mint 2, 4, 6, 8 vagy 10. Ezek közül a 2 nyilván nem lehetséges. A 4 sem, mert ekkor csak teljes gráf esetén lehet minden csúcs fokszáma 3, de akkor mindenki mindenkit ismer. A 6, a 8 és a 10 lehetséges (a gráf csúcsait tömött karika jelöli):     Tehát a társaság 6, 8 vagy 10 fős lehet.