# 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. – Lord Shark the Unknown 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

## 1 Answer

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

• thanks..i have posted the solution from the textbook above as an edit...that solution is more along the lines of what my professor is looking for us to be able to do..if you wouldn't mind taking a look and seeing if you can interpret it for me – rover2 Oct 30 '18 at 15:35