Every planar graph having a vertex of degree $\le 4$ has $X\le 4$

graph theory

I'm reading Richard J. Trudeau's book "Introduction to Graph Theory", in Ch 6, after define chromatic number $X$,

Definition 28. The chromatic number of a graph is the smallest number
of colors with which it can be colored. We shall denote the chromatic
number of a graph by “X”.

it proved the Five Color Theorem, then there goes:

Theorem 17. Every planar graph having a vertex of degree $\le 4$ has $X \le 4$

Proof. Imitate the proof of the Five Color Theorem.

I'm a bit lost here, as the proof of Five Color Theorem given is by mathematical induction on $v$, in short, let $S$ be the statement, “every planar graph with $v$ vertices has $X ≤ 5$.”, the logic is:

(1) $S$ is true for $v=1$.

So now it's to prove: (2) If $S$ is true for $v =k$, then S is true
for $v=k+1$.

Corollary 13 (in the book page 108) guarantees that $G$ possesses at
least one vertex, call it “$A$”, such that the degree of $A$ is $≤ 5$.
Denote by “$G − A$” the subgraph of G obtained by erasing vertex $A$
and all edges incident to vertex $A$. Then $G − A$ is a planar graph
having $k$ vertices, so can be colored with five colors or less.

All that remains now is to extend the coloring of $G − A$ with at most
five colors to a coloring of G with at most five colors.

Case 1. G − A has X < 5. This is obviously ok.

Case 2. G − A has X = 5 and A has degree < 5. This is also obviously
ok.

Case 3. G − A has X = 5 and A has degree 5. This is proved via some
rotating of colouring.

I'm confused here that, it seems this logic does not apply to prove Theorem 17. First of all, given $G$ having a vertex of degree $\le 4$, removing $A$ doesn't guarantee now $G-A$ also keeps this property.

Please enlighten me.

Best Answer

This theorem does not have the kind of nice proof you're looking for.

Some of the kinds of things you could prove using a similar argument include:

  • Every planar graph $G$ with a vertex $v$ of degree $\le 4$, such that $G-v$ is $4$-colorable, is also $4$-colorable.
  • Every planar graph $G$ which is $4$-degenerate ($G$, and every subgraph of $G$, has a vertex of degree at most $4$) is $4$-colorable.
  • If a counterexample to the four-color theorem exists, then the smallest counterexample will not have any vertices of degree $\le 4$.

In all cases, the idea is similar, and you can see this recent question and its answer to find out how. (Briefly, the step you called "rotating of coloring" is mildly more complicated.)

However, as pointed out by Michal Adamaszek in the comments, just "every planar graph with a vertex of degree $\le 4$ is $4$-colorable" is not any easier than the full four-color theorem. Suppose you prove this. Then you can start with any planar graph $G$, add a vertex $v$ of degree at most $4$ (for instance, an isolated vertex), and your theorem will tell you that $G+v$ is $4$-colorable; therefore $G$ is, too.

Related Question