In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
\( {\displaystyle f(G)=f(G\backslash e)+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.[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]
Examples
Spanning Trees
The number of spanning trees t(G) satisfies DC.[3]
Proof. t(G \ e) denotes the number of spanning trees not including e, whereas t(G / e) the number including e. To see the second, if T is a spanning tree of G then contracting e produces another spanning tree of G / e. Conversely, if we have a spanning tree T of G / e, then expanding the edge e gives two disconnected trees; adding e connects the two and gives a spanning tree of G.
Chromatic polynomials
The chromatic polynomial \( \chi _{G}(k) \) counting the number of k-colorings of G does not satisfy DC, but a slightly modified formula (which can be made equivalent):[1]
\( {\displaystyle \chi _{G}(k)=\chi _{G\backslash e}(k)-\chi _{G/e}(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 \( {\displaystyle \chi _{G\backslash e}(k)} \) total G \ e colorings. We need now subtract the ones where u and v are colored similarly. But such colorings correspond to the k-colorings of \( {\displaystyle \chi _{G/e}(k)} \) where u and v are merged.
This above property can be used to show that the chromatic polynomial \( \chi _{G}(k) \) 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 \( {\displaystyle k^{|V(G)|}} \) possible colorings (which is a polynomial in k).
Deletion-contraction algorithm
See also
Inclusion–exclusion principle
Tutte polynomial
chromatic polynomial
Nowhere-zero flow
Citations
Tutte, W.T. (January 2004). "Graph-polynomials". Advances in Applied Mathematics. 32 (1–2): 5–9. doi:10.1016/S0196-8858(03)00041-1.
Dong, Koh & Teo (2005)
"Deletion-contraction and chromatic polynomials" (PDF).
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
