Deleted:Deletion–contraction formula

From WikiAlpha
Jump to: navigation, search
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 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&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]


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&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 <math>k^{|V(G)|}</math> possible colorings (which is a polynomial in&nbsp;k).

Deletion-contraction algorithm

Template:Empty section

See also


  1. 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. 
  2. Template:Harvtxt
  3. "Deletion-contraction and chromatic polynomials".