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.)
Brendan McKay
- 37.7k
- 3
- 80
- 147