# Deleted:Deletion–contraction formula

 The below content is licensed according to Creative Commons Attribution-ShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on http://en.wikipedia.org. The original article might still be accessible here. You may be able to find a list of the article's previous contributors on the talk page.

In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
$f(G) = f(G\smallsetminus e) + f(G / e)$
Here G is a graph, f is a function on the set of vertices of that graph, e is any edge, G&nbsp;\&nbsp;e denotes edge deletion, and G&nbsp;/&nbsp;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 &fnof;&nbsp;=&nbsp;t(G) counting the number of spanning tree 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]

## Properties

As some illustrative examples, the number of spanning trees t(G) satisfies DC.[3] Note below we use a slightly different definition of arboricity that refers to spanning trees (as opposed to forests):
Template:Collapsible sectionThe chromatic polynomial $\chi_k(G)$ counting the number of k-colorings of G is DC, but for a slightly modified formula (which can be made equivalent):[1]

$\chi(G) = \chi(G\smallsetminus e) - \chi(G / e)$Template:Collapsible sectionThis above property can be used to show that the chromatic polynomial $\chi_k(G)$ is indeed a polynomial in&nbsp;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&nbsp;k).