Snarks

Snarks are graphs with an interesting property related to graph coloring. One of the most fascinating coloring results, the four-color theorem states that every map can be colored with 4 colors so that no two neighboring countries have the same color. This is the same as saying that every planar graph can be vertex-colored with 4 colors so that no two adjacent nodes have the same color. The four-color theorem can be restated in terms of snarks as follows: no snark is planar. Informally, a snark is a graph in which every vertex has degree 3 and in which every 3-coloring of edges results in some pair of adjacent edges with the same color. Formally, a snark is a biconnected cubic graph with edge chromatic number 4. There are infinitely many snarks but Petersen's graph is the classic. Since the 70's a lot of strange-looking snarks have appeared in various papers: the Szekeres snark, the Blanusa snark, the Zemfirescu snark, Tietze's graph, etc. Tutte's conjecture that all snarks have the Petersen graph as a minor was proven by Robertson, Seymour and company and is now known as "the snark theorem." Snarks are non-planar and non-Hamiltonian. Even stronger, removing any one node from a snark leaves a Hamiltonian subgraph.