# Domácí úkol 9.2 - moblast
Mapa má vlastnosti rovinného grafu (vrchol = oblast; hrana = společná hranice).
Můžeme také předpokládat, že oblasti stejného státu spolu nesousedí (jinak by se do mapy daly zakreslit jako jedna oblast).
Dále můžeme důkaz omezit na případy, kdy je na mapě alespoň 6 států, jinak by každý stát šlo obarvit jinou barvou.
Víme, že pro $k = 1$ lze mapu obarvit $6$ barvami jen na základě toho, že graf je rovinný.
Matematickou indukcí pak je potřeba dokázat, že pro $k:=k+1$ se počet barev zvýší o $\leq 6$.
Předpokládejme, že jsme nalezli nějaké obarvení pro dosavadní $k$. Nyní $k$ zvýšíme o $1$, čím některé ze států zrušíme a zbývajícím státům přidělíme právě jedno území. Toto území nahradíme barvou některého ze států - příkladové území označme jako $x$ - předpokládejme, že se jedná o stát $A$ s barvou $1$. Je ovšem možné, že jiný stát s barvou $1$ (např. $B$) již s tímto územím sousedí. Tím musíme změnit barvu některého z těchto států - řekněme, že se bude jednat o stát $B$, a přidělíme mu tak barvu (dosavadní barva $+$ $6k$).
Musí nicméně platit, že původní barva "dobytého" území neodpovídá barvě státu, které jsem toto území přidělil. Tím pádem však bude existovat území $y$, které s územím $x$ sousedí, ale nedostalo určitou barvu právě kvůli původní barvě území $x$. To však platí jen v případě, že stupeň daného vrcholu je menší než počet barev Příklad (původní barva je nahoře):
https://ibb.co/s6Sfyxd
Má-li území $y$ stupeň $6k-1$, pak žádný z jeho sousedů nemusí mít shodnou barvu, a proto můžeme předpokládat, že toto území lze patřičně přebarvit.
Toto však nemusí být jediný stát se shodnou barvou, který sousedí s nově dobytým územím (v rovinném grafu není limit nejvyššího stupně).
Nicméně, podle IP existuje pouze $6k$ různých barev kolem nového území.
Pokud by všechny státy s barvou $1$ sousedily s územím, které získal stát $A$, pak by byl již důkaz hotov, jelikož žádný ze států by již neměl barvu $1$. Tím bychom se posunuli na barvu $2$ a postupovali stejně.
Ovšem může existovat stát, který nesousedí s územím $x$, ale získá nové území (označme $y$) v místě, které již sousedí s územím státu $A$