Five color theorem
The five color theorem in graph theory states that any map can be colored with no more than five colors. It is implied by the stronger four color theorem, but can be proved with considerably less effort.
Outline of the proof
First of all, one associates a graph G to the given map, namely one puts a vertex in each region of the map, then connects two vertices with an edge if and only if the corresponding regions share a common border. The problem is then translated into a graph coloring problem: one has to paint the vertices of the graph so that no edge has endpoints of the same color.
The proof then relies on Euler characteristic to show that there must be a vertex V shared by at most five edges, and on the fact that G is planar, i.e. it may be embedded in the plane without intersecting edges.
Now remove V from G. The graph V' obtained this way has fewer vertices than G, so we can assume by induction that it can be coloured with only five colours. Now look at those five vertices V1, V2, V3, V3, V4, V5 that were adjacent to V. If we did not use all the five colours on them, then obviously we can paint V in a consistent way to render our graph 5-coloured.
So we can assume that V1, V2, V3, V3, V4, V5 are coloured with colours 1, 2, 3, 4, 5 respectively.
Now consider the subgraph G13 of G consisting of the vertices that are coloured with colours 1 and 3 only, and edges connecting two of them. If V1 and V3 lie in different connected components of G13, we can reverse the coloration on that containing V1, thus assigning colour number 1 to V and completing the task.
If on the contrary V1 and V3 lie in the same connected component of G13, we can find a path in G13 joining them, that is a sequence of edges and vertices painted only with colours 1 and 3.
Now turn to the subgraph G24 of G consisting of the vertices that are coloured with colours 2 and 4 only, and edges connecting two of them, and apply the same arguments as before. Then either we are able to reverse a coloration on a subgraph of G24 and paint V with, say, color number 2, or we can connect V2 and V4 with a path containing vertices coloured only with colours 2 and 4. The latter possibility is clearly absurd, as such a path would intersect the path we constructed in G13.