Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a set of circles on a plane that don't overlap each other and any of them touches at least 6 other circles. Prove that this set has infinite number of circles.

Well, there seems to be something special about number 6, but the circles are not even of the same radius. If they have the same radius the proof by contradiction would be easy. But this is really hard.

share|improve this question
4  
Possibly easier equivalent problem: Prove that there is no finite planar graph all of whose vertices have degree at least 6. –  Rahul Mar 22 '12 at 8:15
    
well i have no knowledge in graph theory. But don't mind me if that direction leads to something... –  Lorenz Chaos Mar 22 '12 at 8:18

2 Answers 2

up vote 8 down vote accepted

Assume this set of circles was finite. Now consider a circle with minimal radius. Since this circle has minimal radius every circle touching this circle has a greater or equal radius. If some circle has a greater radius this is a contradiction. You can prove this by drawing three circles of equal radius in the plane, touching each other. Joining the centers of these circles you will see that an triangle with equal angles forms. Hence the circles touches $\pi/3$ apart. ($\pi/3$ times $6$ is $2\pi$ so the number 6 is indeed special as you noted). If one of the circles had a greater radius the angle would be greater. Repeating this argument for the minimal circle should yield your result, I think. You can try to fill in all the details yourself. Please let me know if you need any help or if anything is unclear.

Picture showing the equilateral triangle:

enter image description here

Added, due to the responses in the comments: If none of the circles with minimal radius touches a circle with greater radius, then consider the set of all circles with minimal radius. Pick a circle with minimal radius and with its center furthest away from the origin. Such a circle can not touch six other circles with equal radius, since if it did one of them would be further away from the origin.

Added: Just to be clear about this, you can argue as follows. Assume that the set of circles was finite. Pick a circle with minimal radius and center with greatest distance from the origin. By the first part of the argument above, no circle touching this circle can have a strictly larger radius (in that case we would be done), and furthermore by minimality no circle touching that circle can have a strictly smaller radius. Hence every circle touching this circle must have equal radius. But this implies that there is a circle with minimal radius further away from the origin, which is a contradiction.

share|improve this answer
2  
Well, it isn't a contradiction, you have only proved that the minimal circle has six neighbours of the same size. Noone said that the circles have to be different. –  Phira Mar 22 '12 at 9:45
    
You are right, thanks! I have added some lines to hopefully complete the answer. –  user22705 Mar 22 '12 at 10:51
    
thank you. The first part of your argument is exactly what i need. –  Lorenz Chaos Mar 22 '12 at 11:40
    
You are welcome, just note as phira points out, the answer is not complete without the addendum above. I.e. if you pick the circle with minimal radius and center furthest away from the origin, and then argue as above, you should be fine. –  user22705 Mar 22 '12 at 11:57

Here is the argument @Rahul is hinting at. Suppose that you have an arrangement of $n$ circles with disjoint interiors. Now draw a line between the centers of circles that are tangent. In the resulting figure $G$, none of the segments intersect except at endpoints, giving a planar graph (see http://en.wikipedia.org/wiki/Planar_graph) with the circle centers as vertices and tangencies as edges. A fundamental fact about finite planar graphs is that if they have $n$ vertices there are at most $3n-6$ edges (this follows from Euler's formula http://en.wikipedia.org/wiki/Planar_graph#Euler.27s_formula), which is too few for every circle to be tangent to at least $6$ others. (To the OP: this direction does lead to "something". Thinking about why infinite graphs get around this is interesting.)

@user22705's is pretty much complete, though. Consideration of angles says that if a circle in the kind of configuration you're interested in is tangent to one with strictly larger radius, it is also tangent to one with strictly smaller radius. So if there is more than one radius, you end up with an infinite sequence of smaller and smaller circles. The other case is all equal. The tangency points on any circle are then determined: there are six of them, equally spaced. Now check that this implies there must be circles arbitrarily far away from the origin.

share|improve this answer
    
thanks for providing another view to this problem. I will probably take graph theory next semester :) –  Lorenz Chaos Mar 22 '12 at 11:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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