Chromatic Number of Trees

5.1k Views Asked by At

All trees with more than one vertex have the same chromatic number. What is it & Why?

(Is this chromatic number by any chance 2, by definition of what a tree is? Since a tree is acyclic and connected, I think it would have a chromatic number that is strictly one less than 3, which is what a cycle would have to have)

1

There are 1 best solutions below

0
On BEST ANSWER

Trees are bipartite graphs so you can always color them properly with two colors.