[dylanfw]

Could somebody clear up my confusion with these two statements that appear contradictory?

"Do four colors suffice to color any map? — took more than a century to answer (the answer is yes, in case you were wondering)."

and

"Returning our attention to colorings in which connected nodes are supposed to be different colors, we have no guarantee that the five colors in our palette will be sufficient to color the graph G"

How can it be that 4 colors is sufficient for any graph, but for our hypothetical graph G we can't be sure that 5 colors are sufficient?

[philipfweiss]

Four colors is sufficient for a planar graph, but insufficient for a general graph. A planar graph is any graph where the edges can be drawn in such a way that they only intersect at the endpoints (there is a more formal algebraic definition but that helps with the intuition).

[dylanfw]

Thank you! That makes complete sense when I consider the 4 color example of a world map. I didn't even consider that most graphs would have "overlapping borders" on such a map.

An extra thank you for apparently creating a new account to assist me. (I think that's what the green username indicates, at least).

[karmakaze]

The map coloring problem relates to graphs that are planar--can be drawn on a 2D surface without crossing edges. Graphs in general are not planar and so more than 4 colors may be necessary.

[dylanfw]

Thank you! That makes complete sense when I consider the 4 color example of a world map. I didn't even consider that most graphs would have "overlapping borders" on such a map.