Editing Snark (graph theory) (section)

==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]].{{r|gardner}} 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 graph|planar]].{{r|tait}}  The first graph known to be a snark was the [[Petersen graph]]; it was proved to be a snark by [[Julius Petersen]] in 1898,{{r|petersen}} although it had already been studied for a different purpose by [[Alfred Kempe]] in 1886.{{r|kempe}}

The next four known snarks were
*the [[Blanuša snarks]] (two with 18 vertices), discovered by [[Danilo Blanuša]] in 1946,{{r|blanusa}}
*the [[Descartes snark]] (210 vertices), discovered by [[Bill Tutte]] in 1948,{{r|descartes}} and
*the [[Szekeres snark]] (50 vertices), discovered by [[George Szekeres]] in 1973.{{r|szekeres}}
In 1975, [[Rufus Isaacs (game theorist)|Rufus Isaacs]] generalized Blanuša's method to construct two infinite families of snarks: the [[flower snark]]s 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]].{{r|isaacs}} Another infinite family, the [[Loupekine snark]]s, was published by Isaacs in 1976, credited to F. Loupekine. It includes two 22-vertex snarks derived from the Petersen graph.{{r|karcam}}
The 50-vertex [[Watkins snark]] was discovered in 1989.{{r|watkins}}

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.{{r|tietze}} 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.{{r|bghm}}

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.{{r|bghm}} The number of snarks for a given even number of vertices grows at least exponentially in the number of vertices.{{r|skupien}} (Because they have odd-degree vertices, all snarks must have an even number of vertices by the [[handshaking lemma]].){{r|oddness}} [[OEIS]] sequence {{OEIS link|A130315}} contains the number of non-trivial snarks of <math>2n</math> vertices for small values of <math>n</math>.<ref>{{cite OEIS|A130315|mode=cs2}}</ref>