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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .