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?

  • $\begingroup$ 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. $\endgroup$ – I Said Roll Up n Smoke Adjoint Apr 18 '18 at 3:01
  • $\begingroup$ @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$. $\endgroup$ – Mathejunior Apr 18 '18 at 3:03
  • 1
    $\begingroup$ 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. $\endgroup$ – saulspatz Apr 18 '18 at 3:08
  • 3
    $\begingroup$ @Mathbg The circle is the curve. The region bounded by a circle is a disk. $\endgroup$ – saulspatz Apr 18 '18 at 3:11
  • 1
    $\begingroup$ @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? $\endgroup$ – saulspatz Apr 18 '18 at 3:26

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

enter image description here

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.

  • $\begingroup$ Is that a 2D plane? $\endgroup$ – Mathejunior Apr 18 '18 at 3:20
  • $\begingroup$ Yes, it's entirely 2d. $\endgroup$ – B. Mehta Apr 18 '18 at 3:20
  • $\begingroup$ @B.Mehta not enough algebra. J/k wasn't me, I upvoted, but maybe that was premature? $\endgroup$ – I Said Roll Up n Smoke Adjoint Apr 18 '18 at 3:23
  • 1
    $\begingroup$ Ah - and we're back to the circle vs disk issue $\endgroup$ – B. Mehta Apr 18 '18 at 3:35
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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. $\endgroup$ – B. Mehta Apr 18 '18 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.