Let G be a graph of order n whose chromatic polynomial is PG

Let G be a graph of order n whose chromatic polynomial is PG(k) = k(k- l)^n-1 (i.e., the chromatic polynomial of G is the same as that of a tree of order n). Prove that G is a tree.

Solution

As per the chromatic polynomial of G, it is not a complete graph. And by virtue of the property of Chromatic equivalence, Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. Isomorphic graphs have the same chromatic polynomial, but non-isomorphic graphs can be chromatically equivalent too.

All trees on n vertices have the same chromatic polynomial= k(k-1)^n-1

Thus, from the above argument, G is also a tree.