Színezzük ki egy 2009 oldalú szabályos sokszög csúcspontjait két színnel. Bizonyítsuk be, hogy keletkezik azonos színű csúcspontokkal rendelkező egyenlőszárú háromszög!?

És a színezésre nincs valamilyen szabály?

[link]

Biztos van valamilyen "trükkös" gráfelméletes megoldás is, hátha ír olyat valaki...

Nézzünk először egy egyszerűbb feladatot: szabályos 7-szög.

Ábraként nézzük a fenti #2 válasz GeoGebrás ábráját, a csúszkát húzd n=7-re.

Mivel páratlan számú csúcs van, ezért lesz egymás mellett két azonos színű csúcs. Az ábrán ezek az A és G csúcsok, mindkettő kék. Ezekkel szemben van a D csúcs. Ha ez kék, akkor kész vagyunk (ADG háromszög), ezért tegyük fel, hogy D piros.

D szomszédai C és E. Ha mindkettő piros, akkor is kész vagyunk (CDE háromszög). Ha mindkettő kék, akkor az ACE háromszög csupa kék lesz (mint az ábrán), akkor is kész vagyunk. Tegyük tehát fel, hogy C és E közül az egyik piros, a másik kék. Mivel eddig teljesen szimmetrikus minden, ezt bárhogy feltehetjük az általánosság megsértése nélkül, legyen mondjuk a C piros.

Eddig tehát ott tartunk, hogy A,G,E kékek, C és D pedig pirosak. (Az ábra már nem ilyen!)

Ha B piros, akkor a BCD háromszög piros egyenlőszárú lesz, kész vagyunk. Ha viszont B kék, akkor a BAG háromszög lesz csupa kék.

Vagyis szabályos 7-szög esetén biztos, hogy létezik azonos színű egyenlőszárú háromszög, bármilyen is a legfeljebb kétszínű színezés.

Na most 2009 = 7·7·41

Vagyis ha a szabályos 2009-szög minden 7·41-edik élét kiválasztjuk, akkor egy szabályos 7-szöget kapunk. Abban viszont már láttuk, hogy találunk egyszínű egyenlőszárú háromszöget, ami azt jelenti, hogy ugyanez a háromszög jó megoldás a 2009-szögben is.