# 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:

<math>f(G) = f(G\smallsetminus e) + f(G / e)</math>Here

*G*is a graph,

*f*is a function on the set of vertices of that graph,

*e*is any edge,

*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

^{[1]}**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 *ƒ* = *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 <math>\chi_k(G)</math> counting the number of k-colorings of G is DC, but for a slightly modified formula (which can be made equivalent):^{[1]}

<math>\chi(G) = \chi(G\smallsetminus e) - \chi(G / e)</math>Template:Collapsible sectionThis above property can be used to show that the chromatic polynomial <math>\chi_k(G)</math> 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 <math>k^{|V(G)|}</math> possible colorings (which is a polynomial in *k*).

## Deletion-contraction algorithm

## See also

## Citations

- ↑
^{1.0}^{1.1}^{1.2}Tutte, W.T. (January 2004). "Graph-polynomials".*Advances in Applied Mathematics***32**(1-2): 5–9. doi:10.1016/S0196-8858(03)00041-1. https://linkinghub.elsevier.com/retrieve/pii/S0196885803000411. - ↑ Template:Harvtxt
- ↑ "Deletion-contraction and chromatic polynomials". https://www.math.wisc.edu/~svs/475/chromatic.pdf.