Deriving deletion-contraction formula from Subgraph Expansion of Chromatic Polynomial Given a graph $G=(V,E)$, the chromatic polynomial $P(G,q)$ counts the number of $q$-colorings of a graph $G$. It satisfies the deletion-contraction formula:
\begin{equation*}
P(G,q) = P(G-e, q) - P(G/e, q)
\end{equation*}
where $e$ is any edge from $E$ and $G-e$ is obtained by deleting an edge $e$ from $G$ while $G/e$ is obtained by contracting $e$ in $G$.
This is easy to prove: For an edge $e=(u,v)$ in $G$, a proper coloring requires the adjacent vertices $u$ and $v$ to have different colors. 


*

*$P(G-e,q)$ counts the number of $q$-colorings but in this case $u$ and $v$ may have the same color because $u$ and $v$ are not adjacent.

*To compensate the improper colorings, subtract the number of $q$-colorings with $u$ and $v$ having the same color. This corresponds to subtracting $P(G/e,q)$ because if $u$ and $v$ have the same color then they can be merged into one vertex with the same color.


Combining these two cases immediately yields the recurrence above.

Now, I'm just curious whether we can get the same recurrence from a subgraph expansion of chromatic polynomial. A chromatic polynomial can be written as
\begin{equation*}
P(G,q) = \sum_{X\subseteq E}(-1)^{|X|}q^{k(X)}
\end{equation*}
where the summation runs over all the possible subsets $X$ of edges $E$ in $G$ and $k(X)$ is the number of connected components of a subgraph induced by $X$. This is easily obtained from Principle of Inclusion-Exclusion.
If I want to derive deletion-contraction formula from the subgraph expansion, I may begin with a new edge set $E'=E- \{e\}$ and break down the summation as follows:
\begin{equation*}
P(G,q) = \sum_{X\subseteq E'}(-1)^{|X|}q^{k(X)} + \sum_{X\subseteq E'}(-1)^{|X|+1}q^{k(X\cup\{e\})}
\end{equation*}
There's nothing fancy in these summations: The first runs over the edge set which doesn't contain $e$ and the second over those which contains $e$. Handling the extra $-1$ in the second summation, I see that the first summation must yield $P(G-e,q)$ while the second $P(G/e,q)$. The first one is straightforward, but I'm not sure about the second.
Question


*

*What's the best way to prove that the second summation is actually $P(G/e,q)?$ Is it even possible?

*Is there any textbook / paper which derives deletion-contraction from subgraph expansion?

 A: *

*It is quite easy to see explicitly that the second term is $P(G/e,q)$. Consider $F\subset E$ with $e\in F$ (in your notation, $F=X\cup\{e\}$ for $X\subset E'$). Now consider the edge set $\tilde F$ obtained by doing the contraction of the edge $e$, i.e. by removing $e$ and identifying the endpoints. Then it is quite obvious that $|\tilde F| = |F|+1$, as you also have noticed. On the other hand this contraction operation does not change the number of connected components, so $k(F) = k(\tilde F)$. We can then observe that any subset of the edges of $G/e$ can be obtained this way, so clearly
$$ P(G/e,q) = \sum_{\tilde F\subset \tilde E} (-1)^{|\tilde F|} q^{k(\tilde F)} =  \sum_{F\subset E} (-1)^{|F|+1} q^{k(F)} = - \sum_{F\subset E} (-1)^{|F|} q^{k(F)},$$
which is exactly what you wanted to prove.


*I do not know any. Since the deletion-contraction formula can be proven from the quite simple observation that $P(G,q) = P(G+e,q) + P(G\cdot e, q)$, the one you propose seems a more complex route to get to the result.
(I say more complex because one needs to first show that $P(G,q)$ is actually equal to $\sum_{F\subset E} (-1)^{|F|} q^{k(F)}$, but of course if one chooses to start by defining it in this way -as a specialization of the Tutte polynomial for example- and then proving the connection to graph coloring, then this is probably a more direct way.)
