Krdytkyu

I am trying to find the chromatic polynomial for the graph below:

I am using the inclusion-exclusion principle. Here are my bad cases:

$A_1 = {1 text{ and } 2 text{ colored the same }}$

$A_2 = {1 text{ and } 3 text{ colored the same }}$

$A_3 = {2 text{ and } 3 text{ colored the same }}$

$A_4 = {2 text{ and } 5 text{ colored the same }}$

$A_5 = {3 text{ and } 4 text{ colored the same }}$

For $|A_i cap A_j cap A_k|$, there are two cases that can occur:

Either $1,2,3$ are colored the same: $1cdot n^3$ ways for this coloring. Or for example, $1,2,3,4$ are colored the same: $n^2$ ways for this coloring. It was determined during my lecture class that there are $9$ such cases for this type of coloring. However I am having trouble understanding how there are $9$ such cases. Can someone explain?

Here is the inclusion-exclusion method in detail:

• First, we count $|A_1| + |A_2| + |A_3| + |A_4| + |A_5| = 5n^4$. Here, nothing interesting happens: if two vertices are colored the same, we just choose both colors at once.


• Second, we count $|A_1cap A_2| + |A_1cap A_3| + dots + |A_4 cap A_5| = 10n^3$. Here, there are two cases that seem different, but they have the same count. $A_1 cap A_2$ is the first kind: if $1$ and $2$ are the same, and $1$ and $3$ are the same, then we color ${1,2,3}$, then $4$, then $5$. $A_1 cap A_5$ is the second kind: if $1$ and $2$ are the same, and $3$ and $5$ are the same, then we color ${1,2}$, then ${3,5}$, then $4$.


• Next, we count the threefold intersections. Here $A_1cap A_2 cap A_3$ forces $1,2,3$ to be the same, so we color ${1,2,3}$ then $4$ then $5$ in $n^3$ ways. However, this is the only triple intersection of its kind. If we have $A_1 cap A_2cap A_4$, then $1$ and $2$ are the same, $1$ and $3$ are the same, and $2$ and $5$ are the same, so we color ${1,2,3,5}$ then $4$ in $n^2$ ways. The intersection $A_1cap A_2 cap A_3$ is the only one that gives us $3$ things to choose instead of $2$. Altogether, we have $$|A_1cap A_2cap A_3| + |A_1 cap A_2 cap A_4| + |A_1 cap A_2 cap A_5| + |A_1 cap A_3cap A_4| + |A_1 cap A_3 cap A_5| + |A_1 cap A_4 cap A_5| + |A_2 cap A_3 cap A_4| + |A_2 cap A_3 cap A_5| + |A_2 cap A_4 cap A_5| + |A_3 cap A_4 cap A_5| = n^3 + 9n^2.$$
  


• The four-fold intersections also come in two types. Some force all 5 vertices to have the same color and some don't. So for example there are only $n$ cases that fall under $A_1 cap A_2 cap A_4 cap A_5$ since this forces all vertices to be the same color; but there are $n^2$ cases that fall under $A_1 cap A_2 cap A_3 cap A_4$ since vertex $4$ can be different from ${1,2,3,5}$. The only other intersection with $n^2$ cases is $A_1 cap A_2 cap A_3 cap A_5$, and we know this because vertices $4$ and $5$ are the only ones with only one edge. Altogether, we have $$|A_1cap A_2 cap A_3 cap A_4| + |A_1cap A_2 cap A_3 cap A_5| + |A_1 cap A_2 cap A_4 cap A_5| + |A_1 cap A_3 cap A_4 cap A_5| + |A_2 cap A_3 cap A_4 cap A_5| = 2n^2 + 3n.$$
  


• There is only one five-fold intersection, and then there are $n$ colorings it counts because all vertices have to be the same.

Altogether, we get
$$
n^5 - 5n^4 + 10n^3 - (n^3 + 9n^2) + (2n^2+3n) - n = n^5 - 5n^4 + 9n^3 - 7n^2 + 2n
$$
colorings.

The general pattern we see in these calculations is that if we're taking an intersection $A_i cap A_j cap dots$, then the number of cases in that intersection is $n^k$, where $k$ is the number of connected components in the subgraph formed by the edges that $A_i, A_j, dots$ check.