Markström Graph

The Markström graph is a cubic planar graph on 24 vertices which lacks cycles of length 4 and 8 but contains cycles of length 16. (In particular, it contains cycles of lengths 3, 5, 6, 7, and 9-24.)

This graph is related to the open Erdős-Gyárfás conjecture, which posits that any graph with minimum vertex degree 3 contains a simple cycle whose length is a power of two. Gordon Royle and Klas Markström showed that any counterexample must have at least 17 vertices and that any cubic counterexample must have at least 30 vertices. Markström found four graphs on 24 vertices in which the only power-of-two cycles has 16 vertices; the Markström graph is the only planar graph of these four.