Kombinatorika

Jedným z najznámejších problémov v teórii grafov je problém „štyroch farieb“. Teraz ho v krátkosti opíšeme z historického hľadiska. Pri tvorbe máp je požiadavka, aby dva susedné štáty boli zafarbené odlišnými farbami. Vzniká otázka, ktorá bola formulovaná ako hypotéza.

Problém štyroch farieb (Hypotéza - dnes už vyriešená).
Aký je najmenší počet farieb, ktorý stačí na vyfarbenie mapy, ktorú možno nakresliť na glóbuse?

Štáty nahraďme krúžkami, potom „susedné krúžky“ (štáty) spojme čiarou. Dostaneme graf, v ktorom máme zafarbiť vrcholy grafu tak, aby dva vrcholy spojené hranami boli zafarbené rôznymi farbami.

Mapa strednej Európy

Problém štyroch farieb zohral v teórii grafov mimoriadne závažnú úlohu.

1. V roku 1840 sa problémom štyroch farieb zaoberal Möbius.
2. O jeho riešenie sa pokúšal v roku 1850 de Morgan. Od tých čias sa vynaložilo mnoho energie na vyriešenie problému štyroch farieb.
3. Prvý dôkaz uverejnil v roku 1879 Kempe.
4. V roku 1890 Heawood v ňom našiel chybu.
5. Riešenie sa našlo až v roku 1976, keď Appel a Hacken dokázali správnosť hypotézy.

Celkove však bol problém štyroch farieb dôležitým katalyzátorom vývoja princípov teórie grafov. Vyústil v tridsiatych rokoch 20. storočia do vytvorenia systematickej teórie.