Problem of the Week 1231

Defeating the Four Color Theorem

Alice and Bob, moving alternately, will build and color a plane map.

It is convenient to use graphs.

On her move, Alice adds a vertex V (not on an existing edge) and connects V to one or more existing vertices so that no edges intersect. Bob then assigns V a color different from the color of any of its neighbors.

Alice wins if Bob is forced to use a sixth color.

Can Alice win?

Source: Dave Moran, published at FiveThirtyEight, edited by Oliver Roeder.

[View the solution]