Herschel graph

Imagine a shape made of lines and dots.

This shape is called the Herschel graph. It has eleven dots and eighteen lines. You can use these lines to make a solid object. This object has nine flat sides.

Some people try to find a path through it. The path must touch every dot once. But this shape has a trick. You cannot make a path that returns to the start. It is a very special puzzle. It is the smallest shape like this.

Imagine a shape made of dots and lines.

This is the Herschel graph. It has eleven vertices, which are the dots. It also has eighteen edges, which are the lines. This graph is special because it is bipartite. This means you can color the dots with two colors. If you use red and blue, every line connects a red dot to a blue dot.

You can use these lines to build a solid object. This object is a polyhedron. A polyhedron is a 3D shape with flat faces. The shape made by this graph has nine faces. We call this a Herschel enneahedron.

Many people look for a Hamiltonian cycle in a graph. This is a path that visits every dot exactly once and returns to the start. The Herschel graph is the smallest polyhedral graph that has no such cycle. It is a tricky puzzle! You can find a path that touches every dot, but you cannot get back to the beginning.

This graph is named after Alexander Stewart Herschel. He was a British astronomer who studied these kinds of puzzles.

Imagine a puzzle made of dots and lines. In math, we call these dots vertices and the lines edges.

The Herschel graph is a very special kind of pattern. It has eleven vertices and eighteen edges. This graph is bipartite, which is a fancy way to say it has two groups. You can color the dots red and blue so that every line connects a red dot to a blue dot. This pattern is also planar, meaning you can draw it on paper without any lines crossing over each other.

This graph is famous for a missing piece called a Hamiltonian cycle. A Hamiltonian cycle is a path that visits every single dot exactly once and ends up back where it started. You can find a path that visits every dot in the Herschel graph, but you can never close the loop.

Because it has an odd number of dots, the two-color pattern makes a full loop impossible. It is the smallest polyhedral graph that lacks this special cycle. This means it is the simplest 3D shape that cannot solve this specific puzzle. It has fewer edges and faces than any other shape with this problem.

We can turn this flat drawing into a solid 3D shape called a polyhedron. Because the Herschel graph is planar and well-connected, it can form a real object. This object is called a Herschel enneahedron because it has nine faces.

Each of these nine faces is a four-sided shape called a quadrilateral. You can even imagine the shape having different types of faces. Some might be squares or rhombi, while others might look like kites. This shape is a beautiful way to see how math rules turn into physical objects.

This graph is named after a British astronomer named Alexander Stewart Herschel. He studied puzzles involving paths on 3D shapes, like the Icosian game.

While he did not study this exact graph, his work on those puzzles inspired its name. The name appeared in a famous math textbook in 1976. Other mathematicians, like H. S. M. Coxeter, also described it earlier. It is a key example used to show that some math rules do not always work the way we expect.

Math like this shows up in unexpected places, like games. In the game Magic: The Gathering, players use shapes to track their lives. Some shapes are based on the "dual" of this graph. A dual shape is made by looking at the centers of the faces instead of the dots. Because of the way the Herschel graph works, some of these shapes cannot be numbered in a certain way. Players even call one version "the Lich's nemesis" because of a card in the game. It is amazing how a simple set of dots and lines can connect to so many different worlds.

In the mathematical field of graph theory, the Herschel graph serves as a vital example of structural limitations. A graph is a collection of points called vertices connected by lines called edges.

The Herschel graph consists of 11 vertices and 18 edges. It is classified as a bipartite graph, meaning its vertices can be divided into two distinct sets. If you color the vertices with five blue and six red points, every edge will connect a red vertex to a blue one. This specific arrangement is why the graph cannot contain certain types of paths.

The structure of the graph is defined by the connections between its vertices. It contains three vertices of degree four, which means four edges meet at those points. The remaining eight vertices have a degree of three.

Within the graph, each pair of degree-four vertices shares two neighbors that have a degree of three. This creates three distinct four-vertex cycles. Two additional degree-three vertices do not belong to these cycles, but they are each adjacent to three of the other vertices. This specific connectivity makes the graph 3-vertex-connected, meaning you would have to remove at least three vertices to disconnect it.

One of the most important properties of the Herschel graph is its lack of a Hamiltonian cycle. A Hamiltonian cycle is a continuous loop that visits every single vertex in a graph exactly once. While you can find a Hamiltonian path, which visits every vertex without returning to the start,

you cannot close the loop. This is due to its bipartite nature and its odd number of vertices. In any bipartite graph, a cycle must alternate between the two vertex sets. Therefore, a cycle must have an equal number of red and blue vertices, resulting in an even length. Since the Herschel graph has 11 vertices, a cycle covering all of them is mathematically impossible.

The Herschel graph is also a polyhedral graph, which means it can represent the skeleton of a convex polyhedron. According to Steinitz's theorem, any graph that is both planar and 3-vertex-connected can form a polyhedron.

The specific shape formed by this graph is called a Herschel enneahedron. An enneahedron is a polyhedron with nine faces. In this case, all nine faces are quadrilaterals, or four-sided shapes. Depending on how the shape is designed, three faces might be squares or rhombi, while the other six are kites.

History links this graph to the work of Alexander Stewart Herschel, a British astronomer. Herschel studied the Icosian game, which is a puzzle involving finding Hamiltonian cycles on polyhedra like the dodecahedron. Although Herschel did not study this specific graph, the enneahedron represents the smallest convex polyhedron that provides a version of the game with no solution. The name "Herschel graph" was later popularized in a 1976 textbook by John Adrian Bondy and U. S. R. Murty. Other mathematicians, such as H. S. M. Coxeter, had described the graph even earlier.

The graph holds significant status as the smallest non-Hamiltonian polyhedral graph. It has the minimum number of vertices, edges, and faces possible for a polyhedral graph lacking a Hamiltonian cycle. While other graphs like the Goldner–Harary graph also have 11 vertices and no Hamiltonian cycles, none have as few edges as the Herschel graph. This makes it a fundamental counterexample in studies of graph connectivity and pathing. It serves as a boundary case that helps mathematicians understand where certain rules, like Tait's conjecture, begin to fail.

Interestingly, these mathematical properties appear in modern tabletop gaming. In the game Magic: The Gathering, players use polyhedra as "spindown life counters" to track their remaining life points. The dual polyhedron of the Herschel graph is a rectified triangular prism. This dual shape has faces that cannot be numbered in a way that allows for certain continuous transitions. Because of a specific card in the game called "the Lich," which resets a player's life, this specific mathematical limitation led players to name the dual polyhedron "the Lich's nemesis."

Beyond simple shapes, the graph connects to more complex concepts like the medial graph. The medial graph of the Herschel graph is a 4-regular planar graph containing 18 vertices.

Each vertex in this medial graph represents an edge from the original Herschel graph. This structure is 4-vertex-connected and is described as being essentially 6-edge-connected. This means it is very difficult to break the graph into separate pieces by removing edges. These deep connections between vertices, edges, and faces demonstrate how a single mathematical structure can influence many different areas of study.