Deletion–contraction formula

The number of spanning trees ${\displaystyle t(G)}$ satisfies DC.[3]

Proof. ${\displaystyle t(G\setminus e)}$ denotes the number of spanning trees not including e, whereas ${\displaystyle t(G/e)}$ the number including e. To see the second, if T is a spanning tree of G then contracting e produces another spanning tree of ${\displaystyle G/e}$. Conversely, if we have a spanning tree T of ${\displaystyle G/e}$, then expanding the edge e gives two disconnected trees; adding e connects the two and gives a spanning tree of G.

The chromatic polynomial ${\displaystyle \chi _{G}(k)}$ counting the number of k-colorings of G does not satisfy DC, but a slightly modified formula (which can be made equivalent):[1]

${\displaystyle \chi _{G}(k)=\chi _{G\setminus e}(k)-\chi _{G/e}(k).}$

Proof. If e = uv, then a k-coloring of G is the same as a k-coloring of G \ e where u and v have different colors. There are ${\displaystyle \chi _{G\setminus e}(k)}$ total G \ e colorings. We need now subtract the ones where u and v are colored similarly. But such colorings correspond to the k-colorings of ${\displaystyle \chi _{G/e}(k)}$ where u and v are merged.

This above property can be used to show that the chromatic polynomial ${\displaystyle \chi _{G}(k)}$ is indeed a polynomial in k. We can do this via induction on the number of edges and noting that in the base case where there are no edges, there are ${\displaystyle k^{|V(G)|}}$ possible colorings (which is a polynomial in k).

• Dong, F M; Koh, K M; Teo, K L (June 2005). Chromatic Polynomials and Chromaticity of Graphs. World Scientific. doi:10.1142/5814. ISBN 978-981-256-317-0.