[Math] Color the vertices such that no adjacent are the same color

Question

How many ways are there to color the vertices with $n$ colors such that adjacent vertices get different colors?

I know this will use Inclusion-Exclusion.

Since there are $5$ vertices, the total number of ways to color the vertices without restriction is $n^5$.

I am trying to figure out what my sets $A_i$ will be.

$A_1=\{1 \text{ and } 2 \text{ same color}\}$

$A_2=\{2 \text{ and } 3 \text{ same color}\}$

$A_3=\{3 \text{ and } 4 \text{ same color}\}$

$A_4=\{4 \text{ and } 5 \text{ same color}\}$

$A_5=\{1 \text{ and } 3 \text{ same color}\}$

$A_6=\{1 \text{ and } 4 \text{ same color}\}$

$A_7=\{1 \text{ and } 5 \text{ same color}\}$

I am stuck on where to go from here. I know that I need to find:

$|A_i|, |A_i \cap A_j|, |A_i \cap A_j \cap A_k|,…|A_1 \cap A_2 \cap A_3 \cap \dots \cap A_7|$.

$|A_i|=\binom{7}{1} \cdot n\cdot 1\cdot n\cdot n\cdot n = \binom{7}{1} \cdot n^4$

$|A_i \cap A_j|=\binom{7}{2} \cdot n\cdot 1 \cdot 1 \cdot n \cdot n = \binom{7}{2}\cdot n^3$

I am stuck finding the rest.

edit: solution in textbook

$n^5 −C(7,1)×n^4 +C(7,2)×n^3 −{C(7,3)−3)×n^2 +3×n^3} +{(C(7,4)−14)×n+14×n^2}−{(C(7,5)−2)×n+2×n^2}+{C(7,6) −C(7,7)}×n$.

I am trying to attempt to understand how the textbook solution was derived.

Answer 1

Your graph has a very nice pattern for which you can determine the chromatic polynomial without the contraction-deletion recurrence.

Suppose you had $k$ colours. Then vertex $(2)$ can be chosen as any of the $k$ colours, vertex $(1)$ can then be any of the remaining $k-1$ colors and vertex $(3)$ any of the remaining $k-2$ colours. Therefore there are $k(k-1)(k-3)$ ways to colour the left-most triangle.

Now, for any colouring of this triangle, vertex $(4)$ can be coloured $k-2$ ways, namely anything except the colours used for $(1)$ and $(3)$. Likewise, for any colouring of vertices $(1) - (4)$, vertex $(5)$ can also be coloured $k-2$ ways, namely whatever colours $(1)$ and $(4)$ are not. The chromatic polynomial must therefore be $$\chi_G(k) = k(k-1)(k-2)^3.$$