There is a theorem which says that every planar graph can be colored with five colors. It can also be colored with four colors. How can I prove that any planar graph with max degree of $4$, has a four coloring?
Can someone help me prove this?
Asked
Active
Viewed 1,532 times
2
-
Perhaps with the four color theorem? – Ed Pegg Feb 11 '16 at 19:31
-
@EdPegg But, how do I mathematically prove it? – user312732 Feb 11 '16 at 19:55
-
Are you familiar with the standard proof of the $5$-color theorem? It works for $4$ colors as well, as long as you can find a vertex of degree $4$ or less... – Michael Biro Feb 11 '16 at 21:38
-
@MichaelBiro I'm somewhat familiar with it. Could you explain how it would help to prove this case? – user312732 Feb 11 '16 at 22:10
-
@user312732 Ok, I've added it as an answer. – Michael Biro Feb 11 '16 at 22:26
2 Answers
1
[Extended hint, posted as answer because unwieldy as a comment]
Consider a vertex $v$ in your planar graph, so $\deg(v)\le4$.
If $v$ has $3$ or few neighbours, there are at most $3$ colours adjacent to $v$, so we can pick the fourth colour for $v$.
Suppose $v$ has $4$ neighbours. We're only in trouble if all $4$ neighbours have different colours. But that's only a possible problem if all $4$ neighbours have degree $4$ (otherwise, if one of the neighbours had degree $\le 3$, we could ignore it, colour $v$, then recolour the neighbour as above).
So any potential problem reduces to having $\deg(v)=4$, with all $4$ neighbours having degree $4$, and not being able to recolour. Can you think of a way of bringing $K_5$ into the argument? What do you know about $K_5$ and planar graphs?
Edit: While the statements above are true, the proof I'd sketched out in my head didn't work.
Frentos
- 3,041
-
Can you add to your answer. Still having some trouble grasping what you are trying to say. I don't know how to bring in $K_5$ into our proof. – user312732 Feb 11 '16 at 22:09
-
@Frentos Are you suggesting a proof by contradiction where you show the non-existence of such a coloring means that K5 is a subgraph? And then noting that though all vertices of K5 have degree 4, K5 is not planar? – Feb 11 '16 at 22:28
-
-
@barrycarter: Yes, that's where I was headed. I just sat down to elaborate the argument but, if it's possible, it's not as easy as I thought! I thought K5 would pop out quickly from an argument about the Euler characteristic, but it's eluding me. I'll strike out my suggestion. – Frentos Feb 12 '16 at 06:56
0
Choose a vertex $v$ in $G$ and inductively $4$-color $G - v$. If the neighbors of $v$ do not represent all $4$ color classes, choose $v$'s color to create a legal $4$-coloring of $G$.
Otherwise, each of $v$'s neighbors is colored a different color, and suppose they are labeled $v_1,v_2,v_3,v_4$ clockwise in a planar drawing of $G$.
Now, we try to change $v_1$'s color to match $v_3$'s, propagating any forced color changes through the graph. If this is possible, then we can color $v$ with $v_1$'s original color. If it is not possible, then there is an alternating path of the colors of $v_1$ and $v_3$ connecting $v_1$ to $v_3$. Since that path closes a simple curve separating $v_2$ from $v_4$, we can swap $v_2$'s color to $v_4$'s without issue, creating a legal $4$-coloring of $G$.
Michael Biro
- 13,757
-
I have a few questions. What do you mean when you say "inductively 4-color G-v"? Also how does this prove for any planar graph with max degree 4? I'm having some trouble understanding your proof. Could you make it a little clearer if possible? – user312732 Feb 11 '16 at 22:30
-
@user312732 Please look at the proof of the $5$-color theorem. This argument is essentially identical. – Michael Biro Feb 11 '16 at 23:32