Deletion–contraction_formula
Deletion–contraction formula
Formula in graph theory
In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
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]