Way back in 1852, Francis Guthrie conjectured that every map drawn on the plane can be colored so that regions sharing a border have different colors—and only four colors are necessary. This became known as the Four Color Conjecture. In 1880, Tait [16] proved that the Four Color Conjecture is equivalent to a problem of edge coloring graphs. This is where our story begins, because the study of snarks grew from exactly this edge-coloring problem. To avoid confusion, we note that there is no relationship between the English word lsquo;snarkrsquo; (or its derivatives snarky, snarkiness, etc.) and the mathematical term; in fact, the origin of the latter is a pivotal point in our story.

Recall that a graph is a collection of nodes, called vertices, and a collection of connections between these nodes, called edges. You may also remember that a graph is planar if it can be drawn in the plane with no edge-crossings, at which point the regions of the plane demarcated by the graph are called faces. You are less likely to know that a bridgeless graph has no edge whose deletion disconnects the graph, that a 3-regular graph has three edges meeting at every vertex, and that a proper edge coloring assigns a color to every edge of a graph such that no two edges meeting at a vertex have the same color.