JEDEN PUNKT MIT JEDEM VERBINDEN: DIE WENIGSTEN KREUZUNGEN, BEWIESEN

Man setze fünf Punkte auf ein Blatt Papier und verbinde jedes Paar mit einer Kurve: insgesamt zehn Kurven. Sie dürfen sich beliebig krümmen, aber keine darf durch einen dritten Punkt laufen. Wer versucht, jede Kreuzung zu vermeiden, wird scheitern. Bei fünf Punkten ist mindestens 1 Kreuzung unvermeidlich, bei sechs mindestens 3, bei zehn mindestens 60.

Mathematiker nennen ein solches Bild eine Zeichnung des vollständigen Graphen Kₙ – n Punkte, jedes Paar verbunden – und die kleinste Zahl von Kreuzungen, die irgendeine Zeichnung erreichen kann, seine Kreuzungszahl. Martin Balko von der Karls-Universität in Tschechien nennt die Frage „eines der berühmtesten Probleme der topologischen Graphentheorie“.

Die Zählung eines Künstlers

Ende der 1950er-Jahre konstruierte der britische Künstler Anthony Hill Zeichnungen von Kₙ mit genau

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

Kreuzungen, wobei ⌊ ⌋ Abrunden bedeutet. Die Vermutung, dass keine Zeichnung es besser kann, wurde zuerst von Guy veröffentlicht, später von Harary und Hill diskutiert und von Erdős und Guy bekannt gemacht. Sie ist als Harary-Hill-Vermutung oder Guys Vermutung bekannt.

Die Formel steigt schnell:

• 4 Punkte oder weniger: 0 Kreuzungen
• 5 Punkte: 1
• 7 Punkte: 9
• 10 Punkte: 60
• 14 Punkte: 315

Sechs Jahrzehnte Teilantworten

Zeichnungen mit genau Z(n) Kreuzungen gab es für jede Punktzahl; schwierig war der Nachweis, dass keine Zeichnung es besser kann.

Mehr als sechzig Jahre lang wurde das nur für besondere Arten von Zeichnungen bewiesen – etwa wenn alle Punkte auf einer Geraden liegen und jede Kurve auf einer Seite davon bleibt, oder wenn die Punkte auf einer Kugel liegen und jede Kurve den kürzesten Weg nimmt. Balko selbst hatte mit Fulek und Kynčl eine solche Klasse erledigt. Bis 2021 hatten Computer die Formel bis zu 14 Punkten bestätigt. Für sehr große Punktzahlen garantierten die besten allgemeinen Ergebnisse mindestens 98,5 %, dann 98,99 % von Z(n).

Ein Beweis, dann ein klarerer

2026 kündigte OpenAI einen Beweis für jede Punktzahl an, den Balkos Arbeit als „OpenAI Math Release preprint“ aufführt und dem sie das Theorem zuschreibt. Wie dieser Beweis gefunden wurde, sagt die Arbeit nicht. In Balkos Worten ist das Original „relativ kurz“, aber „ziemlich schwer nachzuvollziehen“. Sein Preprint stellt eine vereinfachte Variante vor, die, wie er schreibt, „nur elementare Kenntnisse der linearen Algebra und der Graphentheorie erfordert“. Ein anderer Mathematiker, Gelasio Salazar, bereitet eine eigene, ausführliche Darstellung vor.

Koeffizienten zählen statt Kreuzungen

Da bekannte Zeichnungen Z(n) bereits erreichen, muss nur die untere Schranke bewiesen werden. Dafür braucht es vier Schritte.

1. Ungerade Zahlen genügen. Eine beste Zeichnung lässt sich so umzeichnen, dass Kurven mit einem gemeinsamen Punkt sich nie kreuzen; jede Kreuzung betrifft dann 4 verschiedene Punkte. Man lösche nacheinander jeden von 6 Punkten: Jedes verbleibende Bild mit 5 Punkten hat mindestens 1 Kreuzung, und jede Kreuzung übersteht genau 2 der 6 Löschungen (sie verschwindet, sobald einer ihrer eigenen 4 Punkte gelöscht wird, und übersteht die anderen 2). Also ist die doppelte Zahl der Kreuzungen mindestens 6: mindestens 3, also Z(6). Dieselbe Zählung funktioniert für jede gerade Zahl.
2. Eine Familie von Polynomen. Jeder Punkt erhält seine eigene Zahl. Eine Kreuzung betrifft zwei Kurven, also vier Punkte, also vier Zahlen. Balko verwendet Polynome in vier Variablen, so gewählt, dass die Familie genau Z(n) unabhängige Koeffizienten hat, wenn n ungerade ist – für 7 Punkte 3 × 3 = 9.
3. Zu wenige Kreuzungen lassen Spielraum. Von einem Polynom zu verlangen, an einer Kreuzung zu verschwinden, ist eine Gleichung. Bei weniger Gleichungen als freien Koeffizienten lässt die lineare Algebra immer eine von null verschiedene Lösung übrig. Eine Zeichnung mit weniger als Z(n) Kreuzungen käme also mit einem von null verschiedenen Polynom, das an all ihren Kreuzungen verschwindet; man nehme dasjenige mit dem kleinsten Grad.
4. Die Ebene wehrt sich. Die Geometrie kommt über eine klassische Tatsache ins Spiel: Eine geschlossene Schleife in der Ebene kreuzt eine andere genauso oft von rechts nach links wie von links nach rechts. Mit gut gewählten Gewichten ergibt das eine Summe von Quadraten der Werte des Polynoms, teils positiv, teils negativ gezählt, deren Gesamtwert null ist. Die positiven Terme liegen alle an Kreuzungen, wo das Polynom null ist, also müssen auch die negativen verschwinden. Eine zweite Anwendung der Schleifentatsache macht es durch einen festen Faktor teilbar; die Division ergibt ein von null verschiedenes Polynom niedrigeren Grades mit derselben Eigenschaft – was unmöglich ist, da wir das mit dem kleinsten Grad genommen haben.

Dieses Vorzeichenargument ist Balkos wichtigste Änderung: Es ersetzt das ursprüngliche Argument, das „eine nicht ausgeartete Bilinearform und orthogonale Komplemente“ einbezog. Außerdem beweist er die Schleifentatsache anders und isoliert jeden Punkt direkter.

Andere Netzwerke gleich mit erledigt

Die Antwort bleibt Z(n), wenn man statt der Kreuzungen die Paare von Kurven zählt, die sich überhaupt kreuzen, oder die sich ungerade oft kreuzen – solange sich Kurven mit einem gemeinsamen Punkt nirgendwo sonst treffen. Zusammen mit früheren Reduktionen liefert das Theorem auch exakte Kreuzungszahlen für vollständige Graphen, aus denen einige Verbindungen entfernt wurden, für Kopien eines vollständigen Graphen, die entlang eines Pfades oder um einen geraden Kreis aneinandergereiht sind, und für eine Familie fraktalartiger Netze, die sogenannten erweiterten Sierpiński-Graphen.

Entfernt man eine einzige Kurve aus dem vollständigen Graphen mit 6 Punkten, sinkt sein Minimum von 3 Kreuzungen auf 2; bei 8 Punkten von 18 auf 15.