Chromatic Polynomial for a Graph

Question

I have

The chromatic polynomial for this is given as
$P(G_e,\lambda)=\lambda(\lambda-1)^3$.

How is this calculated?

Answer 1

For a tree with $n$ vertices, you can use deletion-contraction inductively to show the chromatic polynomial is $\lambda(\lambda-1)^{n-1}$

So taking your example and considering deleting the edge $cd$ and contracting $c$ and $d$, you would get $P(G_4,\lambda) = P(G_3,\lambda) P(G_1,\lambda) -P(G_3,\lambda)$ so knowing $P(G_3,\lambda)=\lambda(\lambda-1)^{2}$ and $P(G_1,\lambda)=\lambda$ gives the result.

Answer 2

Say you have $\lambda$ colors available. You can use any of the $\lambda$ colors to color $b$. You can use any color to color $a$, except the one you used to color $b$, so $\lambda-1$ choices for $a$. Similarly, $\lambda-1$ choices for $c$, and then $\lambda-1$ choices for $d$. All up, $\lambda(\lambda-1)^3$.