Virtual Gate Test Series: Algorithms - Tree Coloring

Question

Consider a tree with $n$ nodes where a node can be adjacent to max $4$ other nodes what is the minimum number of colors needed to color the tree so that no two adjacent nodes get the same color?

Comments

Since the given graph is a tree, we can color it in 2 colors. Just try drawing it, with 4 children each, you will get the idea.

---

any graph which does not contains odd length cycle can be colored with <=2 colors, tree satisfies this property

---

we can use chromatic number=1+$d_{max}$(where $d_{max}$ is maximum degree of a vertex).