I recently read about planar graphs and some proofs related to it, in particular I came across the 5-color theorem (any planar graph can be colored in at most 5 colors). I had some trouble understanding the theory behind it (however, I get the 6-color theorem) and came across a proof with helpful images on the mathonline wiki.
I assume the audience here on this site is quite familiar with the proof, so I post only excerpts.
Once again, suppose we have a graph $G$ on $k$ vertices. We know that a connected planar simple graph $G$ contains a vertex of degree 5 or less.
Suppose the $v$ has $deg(v)=5$. If we delete this vertex and all edges incident with $v$, then by our induction hypothesis the resulting graph has a good 5 colouring.
Now we reinsert the vertex $v$. Notice that a good 5-colouring cannot happen if vertex $v$ has neighbours all with different vertex colours since v would then need a 6th colour. We will prove that the neighbours of v cannot all be the same colour now with the following two cases. We will arbitrarily select the red and orange vertices for these cases without loss of generality.
Ok that is basically almost the same as proofing the 6 color theorem. Now:
CASE 1: If there no is red-orange alternating vertex path starting at the red vertex and ending at the orange vertex, then we can interchange the red vertex with an orange vertex and our proof is complete:
Yup, that makes sense to me. We interchange the red and the orange vertex and color $G$ in 5 colors.
CASE 2: If there is a red-orange alternating vertex path starting at the red vertex and ending at the orange vertex, then inspect the yellow and the green vertices. There cannot be an alternating yellow-green vertex path starting at yellow and ending at green since the red-orange path interrupts this path. Hence the yellow vertex can be interchanged green and the proof is once again complete.
What confuses me is "If there is a red-orange alternating vertex path starting at the red vertex and ending at the orange vertex … There cannot be an alternating yellow-green vertex path starting at yellow and ending at green …" Why not? If there is a connection between the red and the orange one, then I can just draw an edge line like this and also connect green and yellow:
And $G$ is still a valid planar graph (can be drawn without overlapping edges). Or what am I missing?
If you look at the colourings in the link you gave, the two vertices we choose first (red-orange in your question, red-green in the link) are supposed to be non-adjacent. The same goes for the second pair. That means that a path connecting the first two must intersect a path connecting the latter two.