Minimal 3-Regular Penny Graph
In a recent post, Each Point has Three Closest Neighbors, I mentioned the following conjecture.
Karabegov’s Conjecture. Any finite planar point configuration in which every point has exactly 3 closest neighbors must contain at least 16 points.
The conjecture was proposed by my dear friend Alexander Karabegov, whom I met in 1974. Wait. What?! I just realized that this was more than 50 years ago. How is that even possible?
After I posted the conjecture, we couldn’t resist working on it. We wandered through different types of graphs and found many cute definitions related to our problem.
A unit distance graph is formed from points in the plane by connecting two points whenever they are exactly distance 1 apart. A matchstick graph is a unit distance graph that can be drawn in the plane with edges of length 1 that do not cross. In other words, it is a unit distance graph that behaves nicely, by being planar. Think of laying matchsticks flat on a table: no overlaps, no chaos.
Here’s the difference visually: the left graph is a unit distance graph, while the right one is a matchstick graph.
Now for the star of the story. A penny graph connects two vertices if and only if their distance is the minimum distance among all pairs of vertices. The name is delightfully literal: imagine placing identical pennies at each vertex so that they do not overlap. Two pennies touch exactly when the corresponding vertices are connected by an edge. A penny graph is a special kind of matchstick graph: two vertices that are not connected are at a distance that is longer than the length of the matchstick.
Finally, a 3-regular graph is a graph where every vertex has degree 3. Three neighbors. No more, no less. They are also called cubic graphs. Not surprisingly, if the vertices of a cube are the vertices of our graph, and the edges of a cube are the edges of our graph, we get a 3-regular graph, as each vertex is incident to exactly 3 edges. Surprisingly, such graphs are not called tetrahedron graphs, as a tetrahedron, too, has each vertex incident to 3 edges. But the tetrahedron graph is special: it is a minimal 3-regular graph.
We wrote a paper Minimal 3-regular Penny Graph, in which we proved the conjecture. The conjecture has officially graduated to a theorem.
Theorem. The minimal 3-regular penny graph has 16 vertices.
Share:
Leave a comment