Every edge on exactly two cycles
Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.
