Deletion–contraction formula

In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:

${\displaystyle f(G)=f(G\setminus e)+f(G/e).}$

Here G is a graph, f is a function on graphs, e is any edge of G, G \ e denotes edge deletion, and G / e denotes contraction. Tutte refers to such a function as a W-function.^[1] The formula is sometimes referred to as the fundamental reduction theorem.^[2] In this article we abbreviate to DC.

R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more, including a function f = t(G) counting the number of spanning trees of a graph (also see Kirchhoff's theorem). It was later found that the flow polynomial is yet another; and soon Tutte discovered an entire class of functions called Tutte polynomials (originally referred to as dichromates) that satisfy DC.^[1]

Examples

Spanning trees

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.

Chromatic polynomials

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-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).

Deletion-contraction algorithm

See also

• Inclusion–exclusion principle
• Tutte polynomial
• Chromatic polynomial
• Nowhere-zero flow

Citations

Works cited

• 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.