5 critical graphs which are planar plus an edge

169 Views Asked by At

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.

1

There are 1 best solutions below

7
On

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.