Graphs and NetworksThe Four Colour Theorem

All of these maps can be coloured with only four different colours, but it is not hard to imagine that other, very complicated maps might need many more colours. In fact, some maps need at least four colours, whenever they contain four countries all connected to each other.

Like before, we can convert a map with countries and borders into a planar graph: every country becomes a vertexan edgea face, and countries which share a borderhave the same colour get connected by an edge:

Now we want to colour the vertices of a graph, and two vertices must have a different colour if they are connected by an edge.