# Color the vertices such that no adjacent are the same color

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.

• That's a chromatic polynomial: there's a recurrence for chromatic polynomials. – Angina Seng Oct 30 '18 at 3:44
• haven't discussed the recurrence in class yet...my professor is looking for a solution similar to how i started it with $|A_i|$ and $|A_i \cap A_j|$ – rover2 Oct 30 '18 at 3:46

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.$$