DRDO CSE 2022 Paper 1 | Question: 10

Question

Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?

Answer 1

We have λ (>=2) different colors. 

ϰ(T)=2 ∀ n>=2 because, A tree wont have an odd length cycle.

Take one vertex to start coloring, let say A, then for A there are λ choices.Now consider any adjacent vertex to A. It can have λ-1 choices (except the color given to A) and all the adjacent vertices of A have λ-1 independent choices (any two adjacent vertices of A can't be adjacent otherwise they will form a cycle). Let B be an adjacent vertex to A then the neighbors of B (except A) also have λ-1 independent choices(set of colors - color given to B) and this process recurses.

In this way one vertex with λ choices other with λ-1  choices. 

∴ total possible colorings=λ*(λ-1)^n-1