Ez egy 6-csúcsú gráf.
Legyen mondjuk zöld él két pont között, ha ismerik egymást, és piros, ha nem ismerik. Minden pontból mindegyikbe megy él, ami vagy zöld, vagy piros.

A feladat annak bizonyítása, hogy van zöld vagy piros háromszög (vagy kölcsönösen ismeri egymást 3 ember, vagy kölcsönösen nem ismeri egymást 3 ember).

Vegyünk egy embert a hatból, vagyis az egyik csúcsot; mondjuk az A nevűt. A maradék öt emberrel ennek az embernek ilyen ismertsége lehet, vagyis a belőle kimenő 5 él iyen lehet:
- 5 piros
- 4 piros 1 zöld
- 3 piros 2 zöld
- 2 piros 3 zöld
stb.
Vegyük észre, hogy vagy van legalább 3 piros él, vagy van legalább 3 zöld.

a) Megy A-ból 3 zöld él.
Ezen élek végpontjait nevezzük B, C, D-nek.
Ha B, C és D között bárhol van zöld él (mondjuk BC között), akkor az ABC háromszög zöld. Ha viszont sehol nincs közöttük zöld él, akkor piros élek vannak, ezért a BCD háromszög piros.

b) Megy A-ból 3 piros él.
Fejezd be hasonlóan...