Graphen und NetzwerkeThe Four Colour Theorem

Alle diese Karten können mit nur vier verschiedenen Farben eingefärbt werden, aber es ist nicht schwer, sich vorzustellen, dass andere, sehr komplizierte Karten viel mehr Farben benötigen. Tatsächlich brauchen manche Karten mindestens vier Farben, wenn sie vier Länder enthalten, die alle miteinander verbunden sind.

Wie zuvor können wir eine Karte mit Ländern und Grenzen in einen planaren Graphen umwandeln: jedes Land entspricht einem Knoteneiner Kanteeiner Fläche, und Länder, die eine Grenze teilendie gleiche Farbe haben werden durch eine Kante verbunden:

Jetzt wollen wir die Knoten eines Graphen einfärben, und zwei Knoten müssen eine andere Farbe haben, wenn sie durch eine Kante verbunden sind.