This is a follow up on an ill posed question. My question is this.

Suppose you are given a graph $G$ which is 5-critical (that is, it is 5-chromatic but if an edge or vertex is removed, it becomes 4 colorable), and such that it has an edge $xy$ which if removed makes the resulting graph planar. The question pertains to the planar part of the graph that remains after removal of the special edge, $G-xy$. My belief is that all the vertices in G are even, or, all the vertices in $G-xy$ are even except for $x$ and $y$. Candidate planar graphs to describe $G-xy$ are subgraphs of maximal planar graphs which have all vertices even except two, and maximal planar graphs which are uniquely colorable and which have exactly two vertices of degree 3 (in which case, I believe, although I might be wrong, all other vertices are even). I have two questions.

  1. Are there any other candidates to describe $G-xy$,

  2. Is it true, as I believe, that maximal planar graphs which are uniquely colorable and which have exactly two vertices of degree 3 have all other vertices of even degree? As per Misha Lavrov’s answer, WHAT IF IT HAS EXACTLY TWO VERTICES OF DEGREE 3, BOTH OF THE SAME COLOR

I might have other questions, but let’s start with these. Let’s hope I got this right this time around

Thank you.

  • $\begingroup$ I now believe that answer to question 1 is no ... I need to make a convincing drawing of this though ... but the answer brings forth a host of other questions ... I will try coming back to this tomorrow. $\endgroup$
    – EGME
    Sep 7, 2020 at 21:21
  • $\begingroup$ The answer to question 2 is no; the graph in my answer to your previous question is a counterexample (its degree sequence is $3,3,4,4,5,5$.) $\endgroup$ Sep 7, 2020 at 21:41
  • $\begingroup$ @MishaLavrov Ah, yes, thank you, that shows I was not paying attention !!! $\endgroup$
    – EGME
    Sep 8, 2020 at 9:58
  • $\begingroup$ @MishaLavrov Let me restate the question. What if it has exactly two vertices of degree 3 of the same color? $\endgroup$
    – EGME
    Sep 8, 2020 at 10:31

1 Answer 1


Here is a $5$-critical graph which is one edge away from being planar, but does not have the property you want:

enter image description here

I obtained it via the Hajós construction, in the following way:

  1. Let $G$ and $H$ be complete graphs on vertices $\{v_1, \dots,v_5\}$ and $\{w_1, \dots, w_5\}$, respectively.
  2. After taking their disjoint union, replace the edges $v_1v_2$ and $w_1w_2$ by edge $v_2w_2$, then identify vertices $v_1$ and $w_1$.
  3. Identify the vertices $v_3$ and $w_3$.

Because we started with two $5$-critical graphs, the result is known to be $5$-critical. It's easy to check that it's one edge away from being planar by inspection. Finally, its degree sequence is $4,4,4,4,4,4,5,7$, which becomes $3,3,4,4,4,4,5,7$ after we delete an edge to make the graph planar.

  • $\begingroup$ Ok, criticality in Hajós constructions is only preserved by the sum, not by vertex identification (although, it can happen). How do you know this is critical after the vertex identification - we know it is 5-chromatic, yes, but critical? Does the removal of any edge make it planar? $\endgroup$
    – EGME
    Sep 8, 2020 at 10:05
  • $\begingroup$ I forgot to say thanks!! $\endgroup$
    – EGME
    Sep 8, 2020 at 10:11
  • $\begingroup$ It's not true that the removal of any edge makes it planar, but I think that's asking for too much. It is true that the removal of any edge makes it $4$-colorable; I checked that in Mathematica as well. $\endgroup$ Sep 8, 2020 at 12:21
  • $\begingroup$ Thanks for the answer. How do you check criticality with Mathematica, do you use the IGraph package? $\endgroup$
    – EGME
    Sep 8, 2020 at 12:58
  • $\begingroup$ That's what I was doing; IGraph's chromatic number function together with trying to delete each edge. Though for graphs as small as this, the built-in chromatic polynomial evaluator should also work. $\endgroup$ Sep 8, 2020 at 13:01

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.