Woran andere seit 40 Jahren scheiterten, wollen drei junge Mathematiker des Georgia Institute of Technology geschafft haben: den Beweis für die Kelmans-Seymour-Vermutung. Ihre dazu ersten, nun im Internet veröffentlichten Ausführungen sehen vielversprechend aus und haben einiges Aufsehen erregt. Doch es sind erst zwei von fünf geplanten langen Arbeiten – eine Menge Text, wenn man bedenkt, dass das ursprüngliche Problem nur einen Satz lang ist.

Zugegeben: Was der Brite Paul Seymor und der Russe Alexander Kelmans unabhängig voneinander in den siebziger Jahren formuliert haben, klingt ganz schön kryptisch. "Jeder 5-zusammenhängende nicht-planare Graph besitzt einen Unterteilungsgraphen des K5", vermuteten sie. Der Laie fragt sich: Bitte was? Der Mathematiker: Ob das stimmt und wenn ja, warum?

Die Graphen, um die es in diesem Fall geht, sind nicht die bananenförmigen Linien auf der Schultafel, es geht um Landkarten oder Netzwerke. Stellen Sie sich Freunde vor, die über Facebook miteinander verbunden sind oder die Ecken eines Würfels, die an den Würfelkanten zusammenhängen. Die Theorie solcher Graphen wird allerorten im Alltag verwendet, in Navigationsgeräten und Routenplanern zum Beispiel oder in den "neuronalen Netzen", mit denen man Handys künstliche Intelligenz, Spracherkennung oder Computern das Go-Spielen beibringt. Sie ist ein vergleichsweise junger Teilbereich der modernen Mathematik. Und sie boomt.

Die Kelmans-Seymour-Vermutung hilft beim Einordnen von Graphen. Der Brite Paul Seymour war im Jahr 1977 auf sie gestoßen, als eine Art Abfallprodukt bei der Planung eines mathematischen Großprojektes. Denn der heutige Princeton-Professor begann damals, die Struktur von Graphen genauer zu untersuchen. Zusammen mit seinem Kollegen Neil Robertson startete er – mit gerade mal 27 Jahren – ein Riesenvorhaben. Im Detail ging es den beiden um die Frage, wie man Graphen nach einfachen Kriterien klassifizieren kann.

Seymours Vermutung spielt in der Welt der "5-zusammenhängenden" und "nicht-planaren" Graphen. Wie zusammenhängend ein Graph ist, ist heute zum Beispiel für Netzwerkadministratoren interessant. Der "Zusammenhang" beschreibt, wie viele Knoten im Netz ausfallen müssen, bis zwei Computer in dem Netzwerk nicht mehr miteinander kommunizieren können. Ein 5-zusammenhängender Graph ist in dieser Hinsicht sehr stabil: In ihm muss man mindestens fünf Knoten zerstören, bis er in Bruchstücke zerfällt. Und planare Graphen lassen sich so auf ein Blatt Papier zeichnen, dass sich keine Kante mit einer anderen überkreuzt.

Einer der kleinsten nicht-planaren Graphen entsteht, wenn man fünf Punkte so verbindet, dass jeder mit jedem anderen in Verbindung steht. Es ergibt sich zum Beispiel ein Drudenfuß in einem Fünfeck – und in jedem Fall Überschneidungen. Diesen Graphen bezeichnen Mathematiker als "K5". Unterteilt man die Verbindungslinien im K5 mit weiteren Zwischenknoten, dann entsteht ein Unterteilungsgraph des K5.

Der Beweis ist harte Arbeit

Seymours Vermutung handelt also von Graphen, die sich nicht ohne Überschneidungen ihrer Kanten zeichnen lassen, und in denen man mindestens fünf Verbindungsknoten löschen muss, bis sie in Einzelteile zerfallen. Die Vermutung besagt: In solchen Graphen sind immer einige der Knoten so verbunden wie die Ecken im Fünfeck-Drudenfuß-Muster des K5 (wobei die Kanten möglicherweise noch durch weitere Knoten unterteilt sind). Was Seymour selbst allerdings nicht beweisen konnte. Seinerzeit war noch zu wenig bekannt darüber, wie kleine Muster in den Graphen deren globale Eigenschaften verändern. Das ist heute anders, und das Autorenteam aus Georgia hat genau dieses Wissen ausgiebig genutzt.

Der Beweis von Dawei He, Yan Wang und Xingxing Yu gleicht einem riesigen Puzzle, in dem Aussagen und Beobachtungen über Strukturen in Graphen zusammengetragen werden. Das ist harte Arbeit, auch für die Leser: Schon die beiden ersten Aufsätze des Teams haben zusammen rund 60 Seiten. Sie lassen ahnen, wie strategisch die Autoren weiter vorgehen wollen.

Die treibende Kraft dahinter ist Xingxing Yu. "Ich habe um das Jahr 2000 begonnen, an ähnlichen Konzepten zu arbeiten und war um 2007 überzeugt, für die Vermutung bereit zu sein." Er wartete weitere Jahre ab, um die richtigen Mitstreiter zu finden. Um 2009 holte er die Doktoranden Yan Wang und Dawei He ins Boot. Mit ihnen gelang allem Anschein nach der Durchbruch – zumindest für Graphentheoretiker ein Grund, die Sektkorken ploppen zu lassen.