Each Point has Three Closest Neighbors
I met Alexander Karabegov during the All-Soviet Math Olympiad in Yerevan. He was one year older than me. By then, when I was still competing in 1976, he was already a freshman at Moscow State University. He proposed the following two related puzzles for the Moscow Olympiad, which I had to solve.
Puzzle 1. You are given a finite number of points on a plane. Prove that there exists a point with not more than 3 closest neighbors.
Just in case, by closest neighbors I mean all points at the minimal distance from a given point. I am sure I solved both puzzles at the time. I leave the solution to the first one to the reader.
Puzzle 2. Can you place a finite number of points on the plane in such a way that each point has exactly 3 closest neighbors?
The last problem has an elegant solution with 24 points chosen from a triangular grid. The story continued almost 40 years later, when Alexander sent me an image (below) of such a configuration with 16 points. He conjectures that this is the minimal configuration.
Karabegov’s Conjecture. Any finite planar point configuration in which every point has exactly 3 closest neighbors must contain at least 16 points.
Can you prove it?
Initially, I didn’t want to give the 24-points solution, but the image above is a big hint, so here you go.
Both constructions reveal the same underlying pattern. The constructions consist of rhombuses formed by two equilateral triangles, and the rhombuses are connected to each other. The 24-point construction consists of 6 rhombuses, while the 16-point construction consists of 4 rhombuses. What will happen if we try the construction with 3 rhombuses? The image below shows such a configuration, which now has extra edges with the shortest distance. We now see 3 points with more than three closest neighbors each, violating the condition. So the conjecture doesn’t break.
So far, every smaller attempt failed — can you prove that 16 is minimal?
Share:
Ross:
I think this is possible to prove by force, but I haven’t put in the necessary time yet.
Some easily proved preliminaries: We need only consider connected planar graphs. The edges will all have the same length. Using houseofgraphs.org there are only 36 3-regular connected planar graphs with less than 16 vertices.
Some types don’t work. For examples prisms: The “vertical” faces of the prism are all rhombuses and must be laid parallel, but then there’s no way to connect the outside ends. That eliminates the prism over the triangle, square, pentagon, hexagon, and heptagon. A similar pattern is a stack of rhombuses with triangles on each end and the two ends connected. That’s another four eliminated (not double counting the triangular prism).
Looking down the list, many of the remaining seem like they can be eliminated by similar considerations.
30 December 2025, 10:12 amRoss:
Follow-up to my earlier comment: I misunderstood the website “House of Graphs” as being a complete database of small order graphs, but it’s not. There seem to be a lot more candidate graphs, so brute forcing is not as easy as I had supposed.
30 December 2025, 10:49 am