theorem; 3-edge-colorability requires a 1-factorization

35 Views Asked by At

My book says the following:

The Petersen graph is 3-regular; 3-edge-colorability requires a 1-factorization.

I'm not sure why they need a 1-factorization. Is it a theorem that supports the requirement of a 1-factorization in the case of the 3-edge-colorability of a 3-regular graph?

1

There are 1 best solutions below

2
On BEST ANSWER

Suppose the edges are colored red white, and blue. Since every vertex is of degree 3, every vertex is incident on a blue edge. Now no two blue edges have a common vertex, so the blue edges are a one-factor.