Deletion–contraction formula

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

${\displaystyle f(G)=f(G\backslash 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 t(G) satisfies DC.[3]

Proof. t(G \ e) denotes the number of spanning trees not including e, whereas 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 G / e. Conversely, if we have a spanning tree T of 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\backslash 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\backslash 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

1. Tutte, W.T. (January 2004). "Graph-polynomials". Advances in Applied Mathematics. 32 (1–2): 5–9. doi:10.1016/S0196-8858(03)00041-1.
2. Dong, Koh & Teo (2005) harvtxt error: no target: CITEREFDongKohTeo2005 (help)
3. "Deletion-contraction and chromatic polynomials" (PDF).