but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem.
Sorry, but the proof of the four-color theorem is much, much more difficult than the proof of this result. (Which is called Kuratowski's theorem and was proved in 1930.)
See http://en.wikipedia.org/wiki/Kuratowski%27s_theorem#Kuratows... for more background on the result that I was saying, and http://people.math.gatech.edu/~thomas/FC/fourcolor.html for more on the four color theorem.
Huh. I know this intuitively from doing those "try to connect the three houses to the three respurces without crossing any lines" kind of puzzles when I was younger—but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem. My (puny) knowledge of topology has been made slightly more concrete. :)