I might be giving a talk to high school students soon. I plan to show them the proof for the six/five coloring theorems and also give a brief discussion of the famous four color theorem.
Why is the four color theorem so much harder to prove than the six/five color theorems? Is there a rather elementary reason for this?
On
I suggest the book Topological Graph Theory by Gross and Tucker. The chromatic number of the torus is 7, I suggest having a torus ready with 7 regions, which, I recall, are hexagons. This was first proved by Heffter in 1891. Heawood's upper bound was 1890; I guess the year discrepancy was about the chromatic number possibly being smaller than seven. Anyway, pages 217 and 218 especially. Also Figure 3.31 on page 137. The hexagon thing is the dual of 3.31.
The chromatic number of a graph imbedded in a genus p surface is $ \chi(S_p) = {\left\lfloor \frac{7 + \sqrt{1 + 48 p}}{2}\right\rfloor} , p \ge 1 $ where ${[x]}$ is is the largest integer not greater than $x$. I was fortunate enough to take Gerhard Ringel 's class on this subject, ( he proved equality in the formula in 1968) . I would still recommend "The Map Color Theorem" as a text in combinatorics . We did not study the proof of the case $ p = 0 $ of course where the chromatic number remarkably fits the formula but proof had been absent until Haken - Appel and the computer proof of 1976. I have no idea why things progressed in that manner, it's a very good question. The history of the proof is a little like the history of the Poincare conjecture.