Snark graph theory

In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to four.

In other words, it is a graph in which every node has three branches, and the edges cannot be colored in fewer than four colors without two edges of the same color meeting at a point. These graphs are part of the proof of the four color theorem.

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.

List of snarks

  • Petersen graph (10 vertices; 1891)
  • Blanuša snarks (two with 18 vertices, discovered in 1946)
  • Descartes' snark (discovered by Bill Tutte)
  • Szekeres snark (50 vertices; 1973)
  • flower snark (20 vertices)
  • double star snark (30 vertices)


This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.