Chromatic Polynomial

Chromatic Polynomial :
For some reason, the topic of chromatic polynomials has
caught the fancy
of my students. And, in particular, the chromatic
polynomial of this graph:

In order to compute
C(G, λ) for the above, I suggested using
the decomposition
theorem. Remove the edge between b,d
and fuse the same vertices in
order to obtain G1 and G2.
G2 will be K3(complete graph with 3
vertices) and for G1,
use the decomposition theorem once
again(i.e. remove the edge between b,c and fuse the same vertices)
to obtain G3 and G4. Now, G4 will again be K3, whereas G3 will
be a simple path of 4 vertices.

After that, I have got two
different and correct solutions
from the students, both of which
don’t use decomposition
theorem.

Solution I :
Suppose, a can be colored in λ ways. Then b
can be colored in λ-1 ways, d in λ-2 ways and
finally c in λ-2 ways.
So, C(G, λ) = (λ)(λ-1)( λ-2)( λ-2)

Note that the order, in which the colors are being assigned,
is important. So, if we assign the colors in a different order, i.e.:
a,b,c,d , the above solution will no longer hold. That is what
confused a bunch of students and one of them(Garveet Parmar)
came up with this solution :

Solution II :
Suppose a can be colored in
λ ways, then b can be colored in
λ-1 ways and c in λ-1 ways. Now, in order to color d,
how many choices do we have? d is connected to all the 3
vertices,
so a casual answer might be : 3. But note that, a and c
can be of same colors. So there are 2 different cases :

Case 1:
a and c are of same colors :
a can be colored in λ ways, b in λ-1 ways, c in 1
way and d in -2 ways.
C1(G, λ) =
(λ).( λ -1).1.( λ-2)

Case 2 :
a and c are of different colors :
a can be colored in λ ways, b in λ-1 ways, c in λ-2
ways and d in λ-3 ways.
C2(G, λ) = λ(λ-1)( λ-2)( λ-3)

Take some time to grasp it and post a comment
if you don’t get it.
Now adding the polynomials C1 and C2, you should get
the final polynomial :
C(G, λ) = C1(G, λ) + C2(G, λ)
= (λ).( λ -1).( λ-2).[ λ-3+1]
= (λ).( λ -1).( λ-2).( λ -2)
which is same as our earlier answer.