In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
f(G)=f(G\setminuse)+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.[1] 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.
The number of spanning trees
t(G)
Proof.
t(G\setminuse)
t(G/e)
G/e
G/e
By Kirchhoff's theorem, the number of spanning trees in a graph is counted by a cofactor of the Laplacian matrix. However, the Laplacian characteristic polynomial does not satisfy DC. By studying Laplacians with vertex weights, one can find a deletion-contraction relation between the scaled vertex-weighted Laplacian characteristic polynomials.[3]
The chromatic polynomial
\chiG(k)
\chiG(k)=\chiG(k)-\chiG(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
\chiG\setminus(k)
\chiG/e(k)
This above property can be used to show that the chromatic polynomial
\chiG(k)
k|V(G)|