Breakthrough!

There was exciting news in the mathematics world recently, when it was announced that Xingxing Yu, Yan Wang and Dawei He from Georgia Tech proved the Kelman-Seymour conjecture.

The 120-page paper containing the proof has been posted to the preprint server arXiv. Given the length of the paper, it will take time for reviewers to verify it. We could wait many months for it to be published in a journal.

What is a graph?

Think: dots and lines.

You might be tempted to think the notion sounds too simple to have any mathematical importance. The field of graph theory focuses on the study of such structures, and they are anything but simple

The dots are called vertices or nodes, and the lines are referred to as edges.

Graphs come up everywhere in nature. For instance, consider networks like neural connections in the brain, or social networks like Facebook, or web pages and their links. Adjacency in graphs is used to model relationships between objects.

Graph theorists are not always concerned with the interpretation of edges in the real world, but rather in the structures found in studying patterns of dots and lines.

We should think of graphs are fluid entities: you can move the vertices around or change the shape of edges, and it doesn’t change the underlying structure. In a planar graph, you can arrange the vertices and edges so that no two edges touch except at a vertex. Think of this as wires connecting circuits, and you don’t want the wires to overlap. For example, overlapping wires might heat up and damage each other.

Certain graphs are easy to identify as planar just by looking at them. Consider the figure below: no two edges touch except at a vertex.

However, it is hard in general to tell if a graph is planar. The following two graphs are important examples of non-planar graphs.

Kuratowski’s theorem

Subdividing is an easy process to make new graphs: given an edge, add new vertices along it to form a path. You can add as many new such vertices as you like. Given a graph G, we let TG denote a subdivision of G. Note that the process of subdivision gives infinitely many new graphs from the one graph G.

If you can find one K₅ or K_3,3 buried in your graph, then the graph is not planar. More generally, if you find a subdivision of K₅ or K_3,3 in your graph, there is no chance to find a planar drawing, as they themselves aren’t planar.

Kazimierz Kuratowski proved in 1930 that a graph is planar exactly when it never contains a graph of the form TK₅ or TK_3,3. This result is so important today it is named Kuratowski’s theorem. While its proof can be found in many graph theory textbooks, it’s not what people would call “obvious”.

Aside: Four color theorem

Planar graphs are famous owing to the four color theorem. We can think of planar graphs as corresponding to maps in an atlas. Each vertex is a country, and two countries are adjacent if they share a border. The ocean is assigned a special vertex (corresponding to the infinite face of the planar graph).

If you want to color a map, then you can’t use the same color for neighboring countries. So when coloring a graph, adjacent vertices must be assigned different colors. We call that a proper coloring.

One could use a different color for each country, but what if you try to be as efficient as possible by using the minimum number of colors? This is called the chromatic number of a graph.

In 1852, Francis Guthrie proposed the conjectured that the chromatic number of a planar graph was at most 4.  After efforts by many generations of graph theorists, the theorem was proven by 1976 by Kenneth Appel and Wolfgang Haken. Interestingly, the proof relies on verification of cases by a computer, and no proof is known that doesn’t need computer assistance.

Enter the Kelmans-Seymour Conjecture

A connected graph is one where there is path connecting any two vertices; roughly, you can’t break it into two separate pieces. The Kelmans-Seymour conjecture says something about connected non-planar graphs.

Some graphs are more connected than others. For example, the following graph or tree as it is called, is connected, but the removal of any vertex disconnects the graph. We say it is 1-connected.

In contrast, in a cycle we need to delete at least two vertices to disconnect the graph. We say this graph is 2-connected.

For a positive integer k, a graph is k-connected if the removal of any k-1 set of vertices does not disconnect the graph. The higher the k, the harder it is to disconnect the graph.

By Kuratowski’s theorem, if a graph is non-planar, then it contains a TK₅ or TK_3,3. Kelmans and Seymour independently considered the case of non-planar graphs with some degree of connectivity. Precisely, they conjectured the following.

Kelmans-Seymour Conjecture: Every 5-connected, non-planar graph contains a TK₅.

The conjecture remained open for 40 years. Until now.

A resolution of the conjecture

The structure of TK₅-free graphs is not well-understood, and the proof of Yu, Wang and He would shed light on that graph class. If the conjecture is true, then it proves Dirac’s conjecture, and it also might shed light on the unresolved cases of the Hajós conjecture.

Why should we care about a proof of the Kelmans-Seymour conjecture?

Pure mathematical research is inspired by our curiosity to understand the patterns of the universe. It has got us this far in our modern world, and we have no idea how far we can go with it.

The world would be boring if we didn’t study such deep mathematical conjectures. Wouldn’t we like to know the answer either way?

We are also driven forward by the undeniable beauty of pure mathematics. Mathematicians work like painters, but our canvas is infinite and we use logic and calculation to compose our works.

Anthony Bonato