Snark (graph theory)
History and examples

Snarks were so named by the American mathematician Martin Gardner in 1976, after the mysterious and elusive object of the poem The Hunting of the Snark by Lewis Carroll. However, the study of this class of graphs is significantly older than their name. Peter G. Tait initiated the study of snarks in 1880, when he proved that the four color theorem is equivalent to the statement that no snark is planar. The first graph known to be a snark was the Petersen graph; it was proved to be a snark by Julius Petersen in 1898, although it had already been studied for a different purpose by Alfred Kempe in 1886.

The next four known snarks were

In 1975, Rufus Isaacs generalized Blanuša's method to construct two infinite families of snarks: the flower snarks and the Blanuša–Descartes–Szekeres snarks, a family that includes the two Blanuša snarks, the Descartes snark and the Szekeres snark. Isaacs also discovered a 30-vertex snark that does not belong to the Blanuša–Descartes–Szekeres family and that is not a flower snark: the double-star snark. The 50-vertex Watkins snark was discovered in 1989.

Another notable cubic non-three-edge-colorable graph is Tietze's graph, with 12 vertices; as Heinrich Franz Friedrich Tietze discovered in 1910, it forms the boundary of a subdivision of the Möbius strip requiring six colors. However, because it contains a triangle, it is not generally considered a snark. Under strict definitions of snarks, the smallest snarks are the Petersen graph and Blanuša snarks, followed by six different 20-vertex snarks.

A list of all of the snarks up to 36 vertices (according to a strict definition), and up to 34 vertices (under a weaker definition), was generated by Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström in 2012. The number of snarks for a given even number of vertices grows at least exponentially in the number of vertices. (Because they have odd-degree vertices, all snarks must have an even number of vertices by the handshaking lemma.) OEIS sequence A130315 contains the number of non-trivial snarks of 2 n {\displaystyle 2n} vertices for small values of n {\displaystyle n}.
detectable_content:number_placeholders[8], length_constraints:number_paragraphs[4], detectable_format:title