10
$\begingroup$

It is possible to arrange congruent circles on the plane in such a way that no two circles overlap and each circle adjoins exactly three other circles. The picture shows an example with 16 circles.

$\hskip1.2in$circles

Now my question is: what is the minimum number of circles required to create an arrangement that satisfies the criteria defined above? (How) can we prove optimality?

$\endgroup$
2
  • $\begingroup$ can the circles have diffirent radii? $\endgroup$
    – quantum
    Jul 7, 2016 at 7:52
  • $\begingroup$ @quantum Nope. Congruent circles. $\endgroup$
    – GOTO 0
    Jul 7, 2016 at 22:53

1 Answer 1

4
+50
$\begingroup$

At this time I do not have a definitive answer, but my remarks on your question are longer than the comment limit.

What we wish to do is find a minimal (in the sense of number of vertices), 3-regular, planar matchstick (aka unit-distance) graph for which there is an embedding that the minimum distance from any vertex to any other non-adjacent vertex is strictly greater than the edge length. There has been some research on this question:

Can you place 24 unit circles in the plane so that each circle is tangent to exactly three other circles? What about 25 unit circles?

It is known that the minimal 3-regular matchstick graph has 8 vertices, but this graph does not satisfy the last condition mentioned above (which I will call "minimum separation"), thus we know that the solution must require an even number of circles greater than 8. I too suspect the minimum is 16 in the configuration you have shown.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .