# Finding a vertex of degree 3 in a penny graph to prove that it can be 4 colored

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!

-
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 '14 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 '14 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 '14 at 5:53
It sounds like a grid graph. – hbm Feb 13 '14 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 '14 at 6:04