Deletion–contraction formula
Formula in graph theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Deletion-contraction formula?
Summarize this article for a 10 year old
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]