2014/03/09 by Robertson, Neil, Seymour, Paul, Thomas, Robin
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1403.2118
Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|>6 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either G\v is planar for some vertex v, or G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.