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.

  • 1
    $\begingroup$ Just to confirm my understanfing, maximal here refers to planarity, i.e., adding any edge breaks planarity? (Equivalently, all faces are triangles) $\endgroup$ – Hagen von Eitzen Sep 6 at 20:40
  • $\begingroup$ @HagenvonEitzen yes, that’s right $\endgroup$ – EGME Sep 6 at 20:41

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.

enter image description here

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks, I completely forgot about maximal planar graphs that are uniquely colorable. Could you address the same question modified as per your answer, (see edited question, an a short moment) ... Thanks!! $\endgroup$ – EGME Sep 7 at 9:43
  • $\begingroup$ @EGME Add a leaf vertex anywhere in the graph. $\endgroup$ – Misha Lavrov Sep 7 at 14:19
  • $\begingroup$ Ok, right, the obvious ... but the problem is that this is not what I am after ... I tried to circumvent the problem of asking the question referring to 5 colorability but maybe I can’t ... I will post the question again in another post and send you a reply here with a link to the question ... thanks $\endgroup$ – EGME Sep 7 at 19:12
  • $\begingroup$ Here is the link to the new question math.stackexchange.com/q/3817759/604076 $\endgroup$ – EGME Sep 7 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.