Originally posted by GregM
Isn't this equivalent to map-coloring? The four-color theorem should apply. Is it possible to completely connect 5 dots to each other with non-crossing lines?
No - but they are connected. The 4-colour theorem applies to any planar
graph (this is a graph - a collection of nodes (points) and vertexes (lines)). A planar graph is any graph that can be drawn on a sphere such that no lines cross.
It can be shown that a graph is not planar if and only if it contains the graph described above (called k[3,3]) or the connected graph on 5 vertexes (k - a pentagon with all nodes connected to all other nodes) embedded in it. This leads quite nicely onto the 5-colour problem.
I know this reads quite awfully - http://tinyurl.com/33zkwr
[wiki] describes it better.