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.

I need to prove that finite penny graphs can be 4-colored without using the 4 color theorem. It's obvious that the graph is planar and I know that I if I can always find a vertex of degree 3 then I can perform induction and complete the proof.

I know that since we have a finite penny graph, if there does not exist a vertex of degree 3 then the graph must be infinite in order to exist. I just don't know where to start to prove that I can always find a vertex of degree 3! It seems so obvious (since there should always be an 'outside' to the graph and the most compact way of having a vertex of degree 4 means I need 3 equilateral triangles which results in a non-convex boundary) but I have no precise proof using contradiction of planarity or something else....

Any tips would be appreciated!

share|improve this question
    
Could you include the definition of a finite penny graph? Also I believe in the usual four color theorem, one only needs to show there is a vertex of degree 4 (or less), not necessarily 3. –  coffeemath Feb 13 at 5:29
    
I found a reference for penny graph, all vertices are circles of same size, and adjacent iff they touch each other. books.google.com/… –  coffeemath Feb 13 at 5:44
    
My line of reasoning for requiring a vertex of degree 3 is as follows: If I could show that there is a vertex of degree 3 then by removing it I can color it's neighbors with colors c1, c2, c3 and finally add the vertex back in as c4. If I had a vertex of degree 4 it's possible for the neighbors to have colors c1, c2, c3 and c4 which forces me to use a color c5 when adding back the vertex. –  suplexor Feb 13 at 5:53
    
It sounds like a grid graph. –  hbm Feb 13 at 5:59
    
@hbm No it is as in my remark (and the link) of above comment, the vertices are same-sized circles, which might not be arranged in a grid form but can be any wich-way, and the "edges" occur when two of the circles touch. –  coffeemath Feb 13 at 6:04
show 1 more comment

1 Answer 1

up vote 0 down vote accepted

You can get away with a vertex of degree four. First note there has to be one, since one can move a remote line parallel to itself until it first meets one of the pennies. Then all the pennies are on one side of that line, and it can be seen that penny has at most four neighboring pennies, which would be arranged around it as four of the total of six which would exactly fit around it making a complete hexagon. The limiting line makes more than four neighbors impossible.

Now the idea of finishing with a vertex of degree four is as follows: Suppose the colors around the vertex go B,R,W,G in circular order (black,red,white,green). Then one can start at the B, and alternately change everything reachable from there (as in a tree). If one gets to the W (so that W would become a B and the "black-white" change did no good), then there is a "black-white" chain connecting those two vertices. But then there cannot also be a "red-green" chain connecting the other two vertices at the same time, and one can start at the red vertex and alternately change reachable vertices between red and green. One will not reach the green vertex touching the starting penny because of the black-white chain connecting the B,W vertices around the starting penny.

I think you could also get three vertices touching a penny if you could show there must be an exterior penny having two different tangents for which all the pennies are on the same side of those tangents. This may be harder to show.

share|improve this answer
1  
Thanks for the explanation of using vertex chains on a vertex of four. Your use the limiting line to find a vertex of degree at most four sparked an idea of using the convex hull of the vertex set to ensure that there is always a vertex of degree 3. Since the graph is finite, a convex hull can be found and thus it is not possible for all the hull vertices to be at least degree 4. Once a vertex of degree 3 is found, induction to prove the graph can be 4 colored is trivial. I dislike having to use the convex hull but currently I don't see a way around it. –  suplexor Feb 13 at 20:40
    
@suplexor Yes I was musing about the convex hull and what the outside boundary would look like, seems almost rigorous to me (not quite, since there may be a few cases to consider) that there has to be a penny with at most 3 neighbors, then you're in business even without the more involved argument re 4 neighbors case. I also don't see a way around convex hull, and to be honest my "move the parallel line" idea would need some kind of proof for a rigorous version. –  coffeemath Feb 13 at 20:47
    
We can start with the line L in contact with one or more pennies, and assuming wlog L is horizontal with all pennies below it, let P be the leftmost penny in contact with line L. Then we can rotate L around P a bit counterclockwise, and still have all the pennies below L. Now the penny P is wedged inside of an angle less than 180, with all the pennies inside that angle, and "clearly" P can have at most 3 neighboring pennies. I think this is nearly rigorous. –  coffeemath Feb 13 at 21:01
add comment

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.