You're reading: Phil. Trans. Aperiodic.

This video about the proof of the Kelmans-Seymour conjecture is adorable

Theorem: every 5-connected non-planar graph contains a subdivision of $K_5$.

The above statement, conjectured independently by Alexander Kelmans and Paul Seymour in the 70s, is very easy to say. And the video below, starring Dawei He, Yan Wang, and Xingxing Yu, makes it look very easy to prove:

It’s like they got Wes Anderson to film an academic PR video. In the normally uninspiring world of maths press releases, it’s quite refreshing. And the written press release is pretty snappy, too. Let’s not make this a thing, though.

However, as “one of those maths whizzes out there”, I wanted to know a bit more about the work than a two-minute video can impart, so I’ve looked up the working-out. There’s a pair of papers building up the proof: “The Kelmans-Seymour conjecture I: special separations”, and “The Kelmans-Seymour conjecture II: 2-vertices in $K_4^{-}$”. They’re decidedly not as aesthetically pleasing as the video: here’s an excerpt from paper 2:


Maybe a publisher will add value to the paper in the form of some line breaks.

Anyway, I thought I’d already been told this theorem as a fact, so congratulations to Dawei He, Yan Wang, and Xingxing Yu for finishing off such a lovely theorem. That’s assuming the proof works: so far, there are just the two preprints on the arXiv and a press release from Georgia Tech. I haven’t been able to find anything from other experts in the field to add credibility to the claim of a proof.

More information

40-Year Math Mystery and Four Generations of Figuring – press release from Georgia Institute of Technology.

Read the papers The Kelmans-Seymour conjecture I: special separations, and The Kelmans-Seymour conjecture II: 2-vertices in $K_4^{-}$. There isn’t much there for the tourist, though.

Finally, I can’t restrain myself from pointing out that paper 1 cites a paper by my maybe-relative, Hazel Perfect, “Applications of Menger’s graph theorem”. So cool!

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>