Snark (graph theory)

Some shapes are very tricky.

They have dots and lines. We try to color the lines. We want to use only three colors. But for these shapes, three colors are not enough!

We call these shapes snarks.

A man named Martin Gardner gave them this name. He liked a funny poem. These shapes are hard to solve. There are many snarks in the world. They can have many dots and lines. Snarks are a fun puzzle to study.

In math, a graph is a set of dots and lines.

Some graphs are very hard to color. We try to color each line with one of three colors. We must not use the same color for two lines that meet at a dot. Most graphs with three lines at each dot can be colored this way. But snarks are different. They need at least four colors.

Martin Gardner gave them this name in 1976. He named them after a poem. The study of these shapes is much older. Peter G. Tait studied them in 1880. He found a link to the four color theorem. This theorem is about coloring maps. He showed that every snark is non-planar. This means you cannot draw a snark on a flat sheet without lines crossing.

The Petersen graph is the smallest snark. It was studied by Julius Petersen in 1898. Other snarks are much larger. The Descartes snark has 210 dots. There are even infinite families of snarks. This means there are endless amounts of them to find.

In math, a graph is a collection of dots connected by lines. Some graphs are very easy to color. Imagine you have three different colored crayons. You want to color every line in a graph so that no two lines meeting at a dot have the same color. Most graphs with exactly three lines at every dot can be done this way.

However, some special graphs are much harder. These are called snarks. A snark is a graph where you simply cannot use only three colors. You will always need at least four colors to finish the job. These shapes are important because they represent the most difficult cases in graph theory.

To be a true snark, a graph must follow certain rules. It must be "cubic," which means every single dot has exactly three lines coming out of it. Scientists also add rules to keep the shapes from being too simple. They usually require the graph to be "bridgeless." A bridge is a single line that, if removed, would split the graph into two separate pieces. Snarks also usually do not have small loops or tiny triangles. Many mathematicians say a snark must have a "girth" of at least five. This means the shortest path that loops back to its start must use at least five lines.

The study of these shapes began long before they had a name. In 1880, a man named Peter G. Tait studied them. He discovered a link to the four color theorem. This theorem is about coloring maps on a flat surface. Tait proved that every snark is "non-planar." This means you cannot draw a snark on a flat sheet of paper without the lines crossing over each other. The name "snark" was not used until 1976. An American mathematician named Martin Gardner chose it. He took the name from a mysterious poem by Lewis Carroll.

There are many different kinds of snarks. The smallest one is the Petersen graph. Julius Petersen studied this graph in 1898. Other snarks are much larger and more complex. For example, the Descartes snark has 210 dots. The Szekeres snark has 50 dots. There are also entire families of snarks that go on forever. Rufus Isaacs found two such families in 1975. One group is called the flower snarks. Another group is the Blanuša–Descartes–Szekeres snarks.

Snarks help mathematicians solve very hard puzzles. One big idea is the snark conjecture by W. T. Tutte. He believed that every snark contains the Petersen graph inside it. This means you could find a version of the smallest snark hidden within any larger one. In 1999, researchers named Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas announced a proof for this. Even though the proof is famous, the full details have not been published yet. Snarks also help us understand how to cover every line in a graph using loops. They are the key to many of the hardest problems in math today.

In the field of graph theory, a snark is a specific type of undirected graph. To understand a snark, you must first understand edge coloring. Imagine a graph made of dots, called vertices, and lines, called edges. In a cubic graph, every vertex has exactly three edges connected to it. An edge coloring is an assignment of colors to these edges. A valid coloring requires that no two edges meeting at the same vertex share a color. For most cubic graphs, you only need three colors to complete this task. However, snarks are special because they cannot be colored with only three colors. They belong to a category called class two graphs, meaning they require at least four colors.

Because some graphs are difficult to color for simple or trivial reasons, mathematicians apply strict rules to define a true snark. First, a snark must be bridgeless. A bridge is an edge that, if removed, would disconnect the graph into two separate pieces. If a graph has a bridge, it is impossible to color it with three colors. Second, snarks are generally required to be simple graphs. This means they cannot have loops, which are edges connecting a vertex to itself. They also cannot have multiple edges connecting the same two vertices. Many mathematicians also require a snark to have a girth of at least five. Girth is the length of the shortest cycle, or loop, in the graph. By forbidding small cycles like triangles or four-vertex loops, researchers ensure the snark is a complex, non-trivial structure.

There are different ways to define these requirements. Some researchers use a "weak snark" definition, which allows for a girth of four. Others use stricter rules, such as requiring the graph to be cyclically 4-edge-connected. This means you cannot disconnect the graph into two parts that both contain cycles by removing only three or fewer edges. These technical constraints help mathematicians focus on the most difficult and interesting examples. Despite these varying definitions, the core idea remains the same: snarks represent the hardest cases for edge coloring in cubic graphs.

The history of snarks began in 1880 with the work of Peter G. Tait. He was studying the four color theorem, which concerns coloring maps on a flat surface. Tait proved that the four color theorem is equivalent to saying that no snark is planar. A planar graph is one that can be drawn on a flat sheet of paper without any edges crossing. Therefore, all snarks are non-planar. The first known snark was the Petersen graph, studied by Julius Petersen in 1898. Interestingly, the name "snark" was not used until 1976. The American mathematician Martin Gardner gave them this name. He was inspired by the elusive creature in the poem "The Hunting of the Snark" by Lewis Carroll.

Mathematicians have discovered many different types of snarks throughout history. The Petersen graph remains the smallest known snark. Other famous standalone examples include the 50-vertex Szekeres snark and the massive 210-vertex Descartes snark. In 1946, Danilo Blanuša discovered two snarks with 18 vertices. In 1975, Rufus Isaacs found ways to create entire infinite families of snarks. He identified the flower snarks and the Blanuša–Descartes–Szekeres family. He also discovered the 30-vertex double-star snark.

Another family, the Loupekine snarks, was published in 1976. These families show that the number of snarks grows at least exponentially as the number of vertices increases.

Snarks are central to several major mathematical conjectures. One of the most famous is the snark conjecture by W. T. Tutte. He suggested that every snark contains the Petersen graph as a minor. A minor is a graph formed by deleting edges or contracting edges of another graph. This would mean the Petersen graph is a fundamental building block for all snarks. In 1999, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas announced a proof for this. While the proof has been published in parts, the complete version remains unpublished. Tutte also proposed a generalization regarding "nowhere zero 4-flows," which relates to how numbers can be assigned to edges in a graph.

Beyond coloring, snarks are important for understanding the cycle double cover conjecture. This conjecture suggests that every bridgeless graph has a collection of cycles that covers every edge exactly twice. Because snarks are the only cubic graphs that cannot be 3-edge-colored, they are the most difficult cases for this problem. If the conjecture is proven true for snarks, it would be true for all graphs. Solving these puzzles helps mathematicians understand the deep connections between shapes, connectivity, and the limits of logic.