Skip to main content
2 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. If not, take a path $P$ of degree 2 vertices that starts and finishes at vertices $v,w$ of degree at least 3. If $v\ne w$, apply induction to $G-P$ (removing the edges and internal vertices of $P$) and it is easy to colour the edgs of $P$. Similarly if $v=w$ and $v$ has degree at least 4.

The remaining case is that $v=w$ and $v$ has degree 3. Then there another path $Q$ from $v$ beginning with the third neighbour of $v$ and continuing until it meets another vertex of degree 3. If $G$ is actually two disjoint cycles joined by a path, colour them ad hoc. Otherwise, remove both $P$ and $Q$ from $G$ and use induction again.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147