The Postal Owl

Mapy s oblastmi

Mějme politickou mapu, kde každý stát má nanejvýš $k$ oblastí, tzn. $\leq k$ stěn této mapy odpovídá jednomu státu a v dobrém obarvení musí dostat stejnou barvu. Dokažte, že každá taková mapa má obarvení nanejvýš $5k+1$ barvami.

(Kapitoly říkají, že je možná potřeba $6(k+1)$, ale mě se to zdá jako chyba. Pokud se vám to $5k+1$ barvami nebude dařit, odevzdejte jako řešení ten nejlepší horní odhad, jaký dovedete.)