40 years to find a Proof

The Kelmans-Seymore conjecture is only one sentence long but thanks to the work of mathematicians at Georgia Institute of Technology, it now has 120 pages of mathematics to (hopefully) back it up.

This conjecture is almost 40 years old! In 1977, Paul Seymore from Princeton University came up with this idea and just 2 years later Alexander Kelmans came to the same conjecture. It states:

“If a graph G is 5-connected and non-planar, then G has a TK5.”[1]

For a short sentence, it is quite a technical statement so let’s break it down. Firstly, a graph is a set of points or vertices which can be connected by straight or curved lines (edges) and a graph is connected if there is an edge connecting any vertex to any other vertex.

source: https://people.hofstra.edu/geotrans/eng/methods/planarnonplanar.html

Planar graphs don’t allow edges to interect

The conjecture also specifies that the graph be non-planar. A planar graph is one which can be drawn in a plane (i.e. it is two dimensional) without any of the edges crossing. Therefore a 5-connected, non-planar graph is one with 5 vertices and with edges of which at least two intersect somewhere other than at the vertices.

Finally, what is a TK5? These are complex graphs which are similar to K5 graphs. K5 looks like a 5 point star enclosed within a pentagon. Kazimierz Kuratowski proved, in 1930, that a graph is planar if it does not contain a graph of the form TK5 or TK3,3. This is known as Kuratowski’s theorem. [2]

k5 and k3,3 graph

K5 graph                                               K3,3 graph

Returning to the Kelmans-Seymore conjecture, now that we understand a little more of it we can appreciate the work that has gone into proving it. In 1990’s Robin Thomas was unsuccessful in finding a proof although he did manage to pass on the progress he had made. Xingxing Yu, a mathematician at Georgia Tech was working on similar concepts in 2000 and in 2007 decided he was ready to tackle this conjecture. In 2008 he brought on a graduate student, Jie Ma, and together they worked through part of the proof. Two years later, graduate students Wang Yu and Dawei He joined the effort and the proof was finally finished. The team currently have two pieces of work published; firstly on 16th November 2015 (The Kelmans-Seymour conjecture I: special separations) and secondly 30th April 2016 (The Kelmans-Seymour conjecture II: 2-vertices in K4). They have another two pieces which have been submitted.  [3]

Xingxing Yu, Wang Yu and Dawei He

Xingxing Yu, Wang Yu and Dawei He

This proof, that has taken just under 40 years to be found, is not actually accepted by the mathematics community yet. First it must pass the scrutiny of many other mathematicians who are currently trying to find fault in the work. The researchers will have about 2 years to try destroy the proof before it can be accepted – a long wait for those who have spent so many years working on it.

However, Wang seems to have faith in their work as he stated, “We spent lots and lots of our time trying to wreck it ourselves and couldn’t, so I hope things will be fine”.[1] If he is right the conjecture will be referred to as: “Kelmans-Seymour Conjecture Proved by He, Wang and Yu.” [1]

Graph theory is a very powerful tool which has some surprising applications including being used to reduce traffic in road networks, find efficient paths in airline networks as well as being used within the design of computer chips. Graph theory has also found applications within evolution of animals and languages, crowd control and the spread of diseases. [4]   Obviously any advances in this sector of Mathematics are incredibly useful and due to the nature of mathematics, discoveries such as this proof often open branches to many more breakthroughs. This proof is therefore not only an important discovery in itself but will now be a stepping stone to new pieces of work such as a proof of Hajos’ conjecture which involves the connection of two graphs.

 

References

1 –  http://www.news.gatech.edu/2016/05/23/40-year-math-mystery-and-four-generations-figuring

2 – https://anthonybonato.com/2016/06/01/the-kelmans-seymour-conjecture-explained/

3 – http://arxiv.org/find/math/1/au:+Yu_X/0/1/0/all/0/1

4 – http://world.mathigon.org/Graph_Theory

 

Picture sources:

Feature image – https://anthonybonato.com/2016/06/01/the-kelmans-seymour-conjecture-explained/

Image 1 – https://people.hofstra.edu/geotrans/eng/methods/planarnonplanar.html

Image 2 – https://anthonybonato.com/2016/06/01/the-kelmans-seymour-conjecture-explained/

Video source – www.youtube.com/watch?v=kJezlZBrbPk

Leave A Comment

Copyright Sci@StAnd 2013