Deletion–contraction formula

Short description: Formula in graph theory

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

$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. The formula is sometimes referred to as the fundamental reduction theorem. 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.

Examples

Spanning trees

The number of spanning trees $t(G)$ satisfies DC.

Proof. $t(G\setminus 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 ${\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):

${\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 ${\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 ${\chi }_{G/e}(k)$ where u and v are merged.

This above property can be used to show that the chromatic polynomial ${\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 $k^{|V(G)|}$ possible colorings (which is a polynomial in k).

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) (in en). Chromatic Polynomials and Chromaticity of Graphs. World Scientific. doi:10.1142/5814. ISBN 978-981-256-317-0.