Two people answered that the Petersen graph is a counterexample. They are correct, but it is more interesting to note that any cubic graph with $4k+2$ vertices is a counterexample. The contracted graph has $2k+1$ vertices an $4k+2$ edges. Each edge colour can appear on at most $k$ edges so at least 5 colors are needed.
Brendan McKay
- 37.7k
- 3
- 80
- 147