Draw some dots on a page. Connect some of the dots with lines (or edges), which don't cross over each other. What you have created is a planar graph
, in the jargon. (In this sort of maths, it's not the exact position of the dots that matters, or whether the edges are straight or curved, but the overall structure of the network.)
Suppose you have done this, in such a way that there are no loops four dots long or five dots long. Perhaps there are loops six dots long: i.e. a dot where you start, do a tour of five other dots, before returning to your starting point, only ever travelling along edges. (Or perhaps there aren't.)
The tricky question is this: can you colour the dots with 3 colours so that pairs of dots which are connected with an edge are never the same colour?
In 1976, Richard Steinberg conjectured that you should always be able to do this. Many people, including Paul Erdős, subsequently tried to prove it. But Steinberg was wrong: in a new paper Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, and Esteban Salgado have created a planar graph with no 4- or 5-cycles, which is not 3-colourable. Click through to the pdf of the paper to see how their graph is built!http://arxiv.org/abs/1604.05108
I got this story from the ever excellent +The Aperiodical