{"id":"arxiv/2609.27168","url":"https://arxiv.org/abs/2609.27168","tags":["math.CO","cs.CG","cs.DM"],"score":0,"title":"Smallest Cubic Non-1-Planar Graphs","domain":"math.CO","source":"arxiv","authors":["Sergey Pupyrev"],"reviews":0,"subject":"math.CO","summary":"A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}