# 5 critical graphs which are planar plus an edge

EDITED as PER ONE ANSWER, EDIT IN CAPS and BOLD

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.

• 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.
– EGME
Sep 7, 2020 at 21:21
• 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$.) Sep 7, 2020 at 21:41
• @MishaLavrov Ah, yes, thank you, that shows I was not paying attention !!!
– EGME
Sep 8, 2020 at 9:58
• @MishaLavrov Let me restate the question. What if it has exactly two vertices of degree 3 of the same color?
– EGME
Sep 8, 2020 at 10:31

Here is a $$5$$-critical graph which is one edge away from being planar, but does not have the property you want: 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.

• 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?
– EGME
Sep 8, 2020 at 10:05
• I forgot to say thanks!!
– EGME
Sep 8, 2020 at 10:11
• 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. Sep 8, 2020 at 12:21
• Thanks for the answer. How do you check criticality with Mathematica, do you use the IGraph package?
– EGME
Sep 8, 2020 at 12:58
• 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. Sep 8, 2020 at 13:01