Four colored planar graphs with two vertices which must be colored the same

Question

QUESTION EDITED, EDIT IN CAPS, AS PER Misha’s answer:

It is known that in maximal planar graphs with exactly two odd vertices, these two odd vertices must be colored the same in any four coloring. It is also possible to construct planar graphs with exactly two odd vertices which are not maximal, and such that in any four coloring the two odd vertices must be colored the same (using Hajós constructions). My question is whether all planar graphs - WHICH ARE NOT (MAXIMAL) PLANAR GRAPHS THAT ARE UNIQUELY 4-COLORABLE - and are such that two vertices must be colored the same have all vertices even except for two. And if so, how is this proved?

As an additional question, are there any references where I could look up and look at some maximal planar graphs with exactly two odd vertices?

Thank you.

Answer 1

There exist other kinds of examples, but for kind of stupid reasons.

Let's start with $K_5 - e$. This is a simple example of a planar graph in which there are exactly two odd-degree vertices, and in any $4$-coloring, those vertices must have the same color - exactly what you're not looking for.

(Here's a quick way to see that this is true, without the general result. If there were a $4$-coloring where the two odd-degree vertices had different colors, we could join them by an edge, and get a $4$-coloring of $K_5$.)

Now take any triangular face of a plane embedding of this graph, and add a new vertex inside this face, adjacent to all three corners. (There is only one way to do this, up to isomorphism, not that it matters.)

• This new graph $G$ is still planar, and in fact still a maximal planar graph, by construction.
• Any $4$-coloring of $G$ gives us a $4$-coloring of $K_5 - e$. So the two odd-degree vertices of $K_5 - e$ (which are not going to be both odd in $G$) still have to have the same color.
• There are now $4$ odd vertices: the new vertex is odd, two of its neighbors change from even in $K_5 - e$ to odd in $G$, and one of its neighbors changes from odd in $K_5-e$ to even in $G$.

Here is a diagram of this graph, and the unique $4$-coloring up to permutation of the colors.

More generally, any Apollonian network will have a unique $4$-coloring up to permuting the colors, and so if you make it large enough, there will be lots and lots of vertices forced to have the same color.