# Is it possible to draw $6$ circles of equal radius each passing through the centres of exactly three others?

Is it possible to draw $6$ circles of equal radius each passing through the centres of exactly three others?

The problem seems to be a direct application of pigeonhole principle but how to use it? May I get a hint?

Here's my take on the Problem : Consider the nodes of the graph as the centres of the circle and the edges as the connection between two circles. Then there will be 9 such edges. Assume that the radius of each circle is $1$ unit. So, how do we ensure that each edge is indeed $\leq 1$ unit?

• I think the problem is not proving that $\leq 1$ but that your graph indeed represents what you want. That it can be drawn and that each circle goes through no more than 3 center points. – I Said Roll Up n Smoke Adjoint Apr 18 '18 at 3:01
• @EnjoysMath the question asks us to show if it's possible or not to draw such a configuration. For the possibility, the only way is to show that the edges are $\leq 1$. – Mathejunior Apr 18 '18 at 3:03
• I think that you say the vertices are the circles, and two are adjacent if they pass through each others' centers. There are only two $3$-regular graphs of order $6$. One is $K_{3,3}$ which is clearly impossible. I can't decide about the other. – saulspatz Apr 18 '18 at 3:08
• @Mathbg The circle is the curve. The region bounded by a circle is a disk. – saulspatz Apr 18 '18 at 3:11
• @B.Mehta Yes it is. I'm so bad at geometry -- even after I realized there were two equilateral triangles, I didn't see the answer. I guess we've proved that the configuration is unique, haven't we? – saulspatz Apr 18 '18 at 3:26

Yes! Draw an equilateral triangle with side length $r$. Then translate the triangle by $r$.

Note: This answer uses the conventional definition of a "circle" to mean the set of points of a fixed distance away from a given point.

• Is that a 2D plane? – Mathejunior Apr 18 '18 at 3:20
• Yes, it's entirely 2d. – B. Mehta Apr 18 '18 at 3:20
• @B.Mehta not enough algebra. J/k wasn't me, I upvoted, but maybe that was premature? – I Said Roll Up n Smoke Adjoint Apr 18 '18 at 3:23
• Ah - and we're back to the circle vs disk issue – B. Mehta Apr 18 '18 at 3:35
• @Mathbg: your figure seems to me to demonstrate the solution is correct. Each point has three others at distance $r$, so if you draw a circle of radius $r$ around each point it goes through the center of three others. – Ross Millikan Apr 18 '18 at 3:38

A cubic (degree 3 for every vertex) graph with 6 vertices and unit distance edges will probably suffice.

In general, a unit distance graph with $n$ vertices and edges with degree $k$ will probably satisfy your problem.

B. Mehta gives one such graph, the prism graph $Y_3$. Though $K_{3,3}$ has 6 vertices and is cubic, it is not a unit distance graph in the plane or 3 dimensions.

Here is the Petersen graph with 10 vertices as a unit distance graph:

Here is the cubic matchstick graph with 8 vertices, the smallest such graph that is also planar:

There are many other examples.

• It can be shown that there cannot be a copy of $K_{2,3}$ in a unit distance graph, so $K_{3,3}$ is not unit distance. In this way, the graph in my answer is unique, and the prism structure shown is unique up to the direction of translation. – B. Mehta Apr 18 '18 at 11:38