Coloring finite number of equal non-intersecting circles
Source: ILL 1979 - Problem 73.
June 5, 2011
combinatorics unsolvedcombinatorics
Problem Statement
In a plane a finite number of equal circles are given. These circles are mutually nonintersecting (they may be externally tangent). Prove that one can use at most four colors for coloring these circles so that two circles tangent to each other are of different colors. What is the smallest number of circles that requires four colors?