In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a deletion-contraction formula / recursion is any formula of the following
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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.
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
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...
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
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time ...
). It was later found that the
flow polynomial is yet another; and soon Tutte discovered an entire class of functions called
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
s (originally referred to as dichromates) that satisfy DC.
Examples
Spanning trees
The number of spanning trees
satisfies DC.
Proof.
denotes the number of spanning trees not including ''e'', whereas
the number including ''e''. To see the second, if ''T'' is a spanning tree of ''G'' then contracting ''e'' produces another spanning tree of
. Conversely, if we have a spanning tree ''T'' of
, 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
counting the number of ''k''-colorings of ''G'' does not satisfy DC, but a slightly modified formula (which can be made equivalent):
:
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
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
where ''u'' and ''v'' are merged.
This above property can be used to show that the chromatic polynomial
is indeed a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
in ''k''. We can do this via
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
on the number of edges and noting that in the base case where there are no edges, there are
possible colorings (which is a polynomial in ''k'').
Deletion-contraction algorithm
See also
*
Inclusion–exclusion principle
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
: , A \cu ...
*
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
*
Chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...
*
Nowhere-zero flow
Citations
{{DEFAULTSORT:Deletion-contraction formula
Graph theory