coefficient of chromatic polynomial I'm currently working on the following graph theory problem:

Let $G$ be a graph of order $n \geq 3$ and let $p_G(x)=\sum_{i=0}^{n-1} (-1)^ia_ix^{n-i}$ be the chromatic polynomial of G. Show that $a_2={e(G) \choose 2}-t(G)$, where $t(G)$ is the number of copies of $K_3$ in $G$.

I know that $a_0=1$ and $a_1=e(G)$. But I'm kind of lost for $a_2$. Would really appreciate any help! Thank you!
 A: Notation:
Let $G$ be a graph and $S \subseteq E(G)$. By a subgraph $H$ induced by $S$ we mean $V(H) = V(G)$, $E(H) = S$. For $S \subseteq E(G)$, let $c(S)$ denote the number of connected components in the subgraph induced by $S$. Let $P_G(x)$ denote the chromatic polynomial of the graph.
The main problem:
We first assume we have this formula for the chromatic polynomial of a graph.
$$
P_G(x) = \sum_{S \subseteq E(G)} (-1)^{|S|} x^{c(S)}.
$$
Then $c_2$ will be affected by choices of $S$ such that the subgraph induced by $S$ has $n-2$ connected components. The subgraph induced by $S$ can be one of three cases:

*

*There is one connected component with 3 vertices, and that component forms a $K_3$.


*There is one connected component with 3 vertices, and that component forms a $P_2$ (path of length $2$, which has $2$ edges).


*There are two connected components with two vertices each.
Case 2) and 3) are all the ways to choose two edges from the graph, which is $\binom{e(G)}{2}$.
Case 1) are basically all the ways to choose a triangle from the graph, which $t(G)$. Hence the number of ways is $\binom{e(G)}{2} \color{red}{-} t(G)$. The minus sign comes from the fact that in Case 2) and 3), $|S| = 2$ is even, while in Case 1), $|S| = 3$ is odd. As per the formula, the sign is different.

Proving the formula:
We say a $k$-colouring $c: V(G) \to [k]$ conflicts at edges $S \subseteq E(G)$ if for each edge $uv \in S$, $c(u) = c(v)$. It is easy to show that the number of $k$-colourings that conflicts at $S$ is $k^{c(S)}$.
By definition, $P_G(x)$ counts the number of colourings which do not conflict at any subset of edges in $E(G)$. Hence, by inclusion-exclusion:
\begin{align*}
  \{\text{colourings not conflicting at any subset of $E(G)$}\} &= \{\text{all colourings}\} \\
    &- \{\text{colourings conflicting at $1$ edge of $E(G)$}\} \\
    &+ \{\text{colourings conflicting at $2$ edges of $E(G)$}\} \\
    &- \{\text{colourings conflicting at $3$ edges of $E(G)$}\} \\
    & \vdots \\
    &+ (-1)^{|E(G)|} \{\text{colourings conflicting at all edges of $E(G)$}\} 
\end{align*}
Using the fact that the number of $k$-colourings that conflicts at $S$ is $k^{c(S)}$ gives the result.
