Skip to main content
3 of 3
added 741 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

No, an odd cycle is a counterexample. Similarly if there is a component which is an odd cycle. But maybe these are the only cases? (Haha, I forgot to click "save" and Mikhail beat me.)

Ok, wlog $G$ is connected. If all vertices have degree 2, it depends on odd or even length, as above.

The cases where $G$ is a dumbbell or a theta-graph (two vertices with three paths joining them), or a collection of cycles with one common vertex, are easy to colour by ad hoc methods. So suppose $G$ is not one of those. Then there is a path $P$ of (possibly 0) degree 2 vertices between two distinct vertices of degree at least 3. Remove the edges and internal vertices of $P$ and apply induction. Then put back $P$ and easily colour its edges as well.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147