Grafice și rețeleThe Four Colour Theorem

Toate aceste hărți pot fi colorate doar cu patru culori diferite, dar nu este greu de imaginat că alte hărți foarte complicate ar putea avea nevoie de mult mai multe culori. De fapt, unele hărți au cel puțin patru culori, ori de câte ori conțin patru țări toate conectate între ele.

Ca și înainte, putem converti o hartă cu țări și granițe într-un grafic plan: fiecare țară devine un vertex o margine o față și țările care au o frontieră au aceeași culoare să fie conectate de o margine:

Acum vrem să colorăm vertexurile unui grafic, iar două vârfuri trebuie să aibă o culoare diferită dacă sunt conectate de o margine.