5
$\begingroup$

How to prove an implication

Every bridgless planar 3-regular graph G is 3-edge colorable.

I know:

  1. From Vizing Theorem, that I can color G with 3 or 4 colors.
  2. I have a hint to use that we have an embeeding in plane (as a corrolary of 4CT).
  3. Induction is clearly not a right way since G-v does not have to be 2-connected.
  4. If it is 3-edge colorable, I need to use all 3 edge colors in every vertex.

What I do not know:

  1. Obviously, a full solution. :)
  2. How should I use an assumption of 2-connectivity (this seems to me as an essential thing).

What I think could work out:

  1. Prove that G is Hamiltonian, then my exercise is a simple corrolary.

Any help?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $G$ be a bridgless planar $3$-regular graph and suppose it is given a plane embedding. Then by the four-colour theorem, there exists a proper $4$-face-colouring of $G$, say using $(1,2,3,4)$.

Now notice that since $G$ is bridge-less, all edges see two distinct faces which have different colours.

Colour the edges which see faces coloured $1,2$ or $3,4$ blue. Colour edges which see faces coloured $1,3$ or $2,4$ red. Colour the edges which see faces coloured $1,4$ or $2,3$. Note this colours all edges in our graph as every edge sees two distinct faces.

Since $G$ is $3$-regular, this colouring is a $3$-edge-colouring of $G$. If two adjacent edges were given the same colour, then either they both see the same coloured faces, or they each see two different faces.

In the case where both see the same coloured faces, this implies $G$ has a vertex of degree $2$. In the other case where the edges see all different faces, that implies that $G$ has a vertex with degree greater than $3$.

$\endgroup$

You must log in to answer this question.

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