Breakthrough Proof 40 Years Later
Paul Seymour and Alexander Kelmans each came to the same conclusion related to graph theory in 1977 and 1979, respectively. This conclusion became called the Kelmans-Seymour Conjecture. The conjecture is one that builds upon simple concepts from graph theory that we learned in class, and is actually fairly easy to understand. Recall what it means for a graph to be connected. Consider a graph G = (V, E) with a set of nodes V and set of edges E. G is connected if for any two nodes A and B in V, there is some path using the edges from E that connects A and B. There are also different levels of connectedness. A 1-connected graph is a graph where removing only one node disconnects the graph. In a 2-connected graph (like the example shown below), one must remove at least two nodes to disconnect the graph. In the general case, a k-connected graph is a graph in which k is the minimum number of nodes that need to be removed in order to disconnect the graph.
2-connected graph
The conjecture itself is actually pretty simple, relative to how complicated it was to prove. The Kelmans-Seymour Conjecture states that every non-planar 5-connected graph has something in it called a TK5. A TK5 is a formation that resembles a five-point star with a pentagon around it, and it is known that if a graph contains such a subdivision that graph is not planar (by Kuratowski’s Theorem). The implications of the conjecture are that you are guaranteed to find a TK5 in your graph is it is 5-connected and non-planar. While a simple enough statement, it took 39 years and at least 6 mathematicians to prove it. As of now, the 120-page proof is complete but is under review. For the next couple of years, other researchers are going to analyze the proof attempting to find holes in it. The creators of the proof are confident it will stand, though. This proof not only provides proof to the Kelmans-Seymour Conjecture, but it also proves some other open conjectures: Dirac’s conjecture and the Hajos conjecture.
With graph theory being talked about since the 1700s, it’s clear it is still a developing field of mathematics to this day. It is inspiring to see that even after decades of not being able to prove something, these mathematicians and researchers did not give up and actually completed it. While this conjecture and proof have no mention of positive/negative relationships or directed edges, it is still very relevant to the graph theory we learned in class and has its own implications about connectedness in any kind of network that can be represented by a graph.
http://phys.org/news/2016-05-year-math-mystery-figuring.html
The Kelmans-Seymour conjecture explained