Zu Beginn meines Mathematik-Studiums gab mir ein Freund eine Aufgabe: Ich sollte ihm erklären, wie viele Möglichkeiten es gibt, das Haus vom Nikolaus in einem Zug zu zeichnen – und warum manche Wege funktionieren und andere nicht. Es klang kinderleicht und ich hätte nicht gedacht, dass es dazu führen würde, dass ich stundenlang über Knoten, Brücken und den Instagram Algorithmus nachdenken würde.

Die Antwort auf die erste Frage war leicht zu finden: Von jeder der beiden unteren Ecken gibt es 44 Möglichkeiten, das Haus zu zeichnen. Für alle, die sich noch überzeugen lassen wollen: Auf der Wikipedia-Seite des Hauses vom Nikolaus sind Videos zu finden, in denen alle Möglichkeiten nebeneinander aufgemalt werden.

Die Frage, warum alle 44 funktionieren, führt zu Leonhard Euler, der sich im 18. Jahrhundert mit dem Problem befasste, ob es einen Rundweg durch die Stadt Königsberg gibt, bei dem jede Brücke genau einmal überquert wird. Euler bewies, dass das für die Stadt Königsberg nicht möglich war und fand gleichzeitig heraus, was gegeben sein muss, damit es klappt. Für eine Intuition, wie Euler damit geklärt hat, warum wir das Haus vom Nikolaus nur von den unteren beiden Ecken aus malen können, braucht man nur Zettel und Stift.

Man malt das Haus vom Nikolaus auf und bezeichnet jeden Eckpunkt als Knoten und jede Kante – nun ja, als Kante. Der Schnittpunkt der beiden Diagonalen im Inneren des Hauses ist kein Knoten, weil man dort beim Malen keine Abzweigung nehmen darf. Dieses Konstrukt aus Knoten und Kanten heißt Graph. Analog sind beim Königsberger Brückenproblem die Landstriche, welche der Fluß voneinander abgrenzt, die Knoten und die Brücken und die Kanten.

Graphen lassen sich überall wiederfinden. Eine Freundesgruppe, bei der manche mit allen befreundet sind, andere nur mit einigen wenigen, lässt sich ebenso als Graph darstellen. Die Personen sind die Knoten und die Freundschaften die Kanten. Der Instagram-Algorithmus braucht dieses Konzept dementsprechend auch, um das soziale Umfeld der Nutzer zu analysieren. Anders gesagt: Graphentheorie – Im 18. Jahrhundert hat jemand nach dem kürzesten Transportweg gesucht und heute bekommen wir passgenaue Reels zugespielt.

Euler bewies nun, dass ein Rundweg, bei dem jede Kante genau einmal abgegangen wird, nur unter folgender Bedingung möglich ist: Wenn genau zwei der Knoten eine ungerade Anzahl an angrenzenden Kanten haben – wie beim Haus vom Nikolaus – oder wenn die Anzahl bei allen Knoten gerade ist.

Die grobe Idee dazu ist folgende: Man male sich eine weitere Kante in das Haus vom Nikolaus, welche die beiden unteren Eckpunkte verbindet. Da dort schon eine ist, die unterscheidbar bleiben soll, malt man zum Beispiel ein „U“ unten ans Haus dran. Nun haben alle Knoten eine gerade Anzahl angrenzender Kanten – es ist nun ein sogenannter Eulerkreis. Hierfür finden wir immer einen Weg, der jede Kante einmal abgeht und wieder beim Startpunkt ankommt. Letzteres muss gelten, weil der Startpunkt sonst eine ungerade Anzahl an angrenzenden Kanten hätte. Einen solchen Knoten gibt es in unserem erweiterten Nikolaus-Haus aber nicht. Der Kniff ist nun, dass wir das hinzugefügte „U“ wieder herauswerfen und so einen Schwung vom einen unteren Eckpunkt zum anderen finden.

Nicht jeder Weg führt jedoch ans Ziel. Deshalb bleibt noch eines zu tun: Alle 54 Varianten systematisch durchprobieren. Zehn davon enden in einer Sackgasse und 44 – aber das haben wir ja schon geklärt – funktionieren.