Anna és Bálint a következő játékot játsszák: Anna rajzol egy tetszőlegesen nagy üres (azaz él nélküli) gráfot, majd egyesével behúz tetszőleges éleket, amelyeket Bálint közvetlenül a behúzás után kékre vagy pirosra színez. További szabály, hogy az így keletkező gráfban minden csúcs foka legfeljebb k lehet, és k értékében előre megállapodnak. Melyik az a legkisebb k, amely mellett Anna ügyes játékkal mindenképpen létre tud hozni egy 2011 hosszúságú egyszínű utat?

Megoldás: 

$ k\ge3 $