Number of ways to color a square graph with diagonal line using principle of Inclusion and Exclusion How many ways can we color the graph if adjacent vertices receive different colors ?

It's easy to see that the answer is $n(n-1)(n-2)^2 = n^4-5n^3+8n^2-4n$, where $n$ is the number of colors (fix a color to the top left vertex, for the top right vertex we can choose $n-1$, for the bottom left we can choose $n-2$ and for the bottom right we can also choose $n-2$).
But how can I explain this answer or proof it by using the Principle of Inclusion and Exclusion ? (about explain I mean what each of this terms mean $-5n^3+8n^2-4n$)
 A: There are $n^4$ ways to assign colors to the vertices, without regards to neighboring vertices being different. The graph has five edges, call them $e_1,\dots,e_5$. For each $i\in \{1,\dots,5\}$, let $C_i$ be the set of colorings where both endpoints of $e_i$ are the same color. Then the number of proper colorings is
$$
n^4-|C_1\cup \dots \cup C_5|.
$$
You can now directly apply the principle of inclusion-exclusion to this expression, resulting in
$$
n^4-|C_1|-|C_2|-\dots-|C_5|\\
+|C_1C_2|+|C_1C_3|+\dots+|C_4C_5|\\
-|C_1C_2C_3|-\dots-|C_3C_4C_5|\\
+|C_1C_2C_3C_4|+\dots+|C_2C_3C_4C_5|\\
-|C_1C_2C_3C_4C_5|
$$
You then just need to work through all of those intersections. Here is a semi-thorough sketch.

*

*It is not hard to show $|C_1|=\dots=|C_5|=n^3$, resulting in the $-5n^3$ term.


*The pairwise intersections contribute $10n^2$. Suppose that $e_1,e_2,e_3,e_4$ are the edges of the square, numbered in anti-clockwise order with $e_1$ on top, and $e_5$ is the diagonal.

*

*You can show that $|C_1C_2|=n^2$, since to color something in $C_1$ and $C_2$, the three vertices spanned by $e_1$ and $e_2$ must all be the same color, while the remaining vertex can be colored freely. The same applies to $|C_iC_j|$ whenever $e_i$ and $e_j$ share an endpoint.


*We also have  $|C_1C_3|=|C_2C_4|=n^2$. This time, colorings in $C_1C_3$  require making two choices, one for the two endpoints of $e_1$, the other for the two endpoints of $e_3$.




*For the triple-wise intersections, the contribution will be $-2n^2-8n$. Here, there are two cases, based on whether the three selected edges span the entire graph, or whether they make a triangle. For example, $|C_1C_2C_3|=n$, but $|C_2C_3C_5|=n^2$.


*The four-way intersections contribute $+5n$, since any choice of four edges will span the entire graph. Similarly, $|C_1\dots C_5|=n$.
Adding these all up leads to $n^4-5n^3+8n^2-4n$.
