Skip to main content
added 741 characters in body
Source Link
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

The cases where $G$ is a dumbbell or a theta-graph (two vertices with three paths joining them), takeor 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 that starts and finishes atbetween two distinct vertices $v,w$ of degree at least 3. If $v\ne w$, apply induction to $G-P$ (removingRemove 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 3apply induction. 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 bothput back $P$ and $Q$ from $G$ and use induction againeasily colour its edges as well.

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.

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.

added 741 characters in body
Source Link
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.

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.)

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.

Source Link
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.)