Grafos e RedesThe Four Colour Theorem

Todos esses mapas podem ser coloridos com apenas quatro cores diferentes, mas não é difícil imaginar que outros mapas muito complicados pode precisar de muito mais cores. De fato, alguns mapas precisam de pelo menos quatro cores, sempre que contenham quatro países, todos conectados um ao outro.

Como antes, podemos converter um mapa com países e fronteiras em um gráfico planar: todo país se torna um vérticean edgea face e países que compartilham uma bordahave the same colour conecte-se por uma aresta:

Agora, queremos colorir os vértices de um gráfico, e dois vértices devem ter uma cor diferente se estiverem conectados por uma aresta.