# Deleted:Tutte–Grothendieck invariant

The below content is licensed according to Creative Commons Attribution-ShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on http://en.wikipedia.org. The original article might still be accessible here. You may be able to find a list of the article's previous contributors on the talk page. |

In mathematics, a

**Tutte–Grothendieck (TG) invariant**is a type of graph invariant that satisfies a generalized deletion–contraction formula. Any evaluation of the Tutte polynomial would be an example of a TG invariant.

^{[1]}

^{[2]}

## Definition

A graph function *f* is TG-invariant if:^{[2]}

<math>f(G) = \begin{cases} c^{|V(G)|} & \text{if null} \\ xf(G/e) & \text{if } e \text{ is a loop} \\ yf(G \backslash e) & \text{if } e \text{ is a coloop or bridge} \\ af(G/e) + bf(G \backslash e) & \text{else} \end{cases}</math>

Above *G* / *e* denotes edge contraction whereas *G* \ *e* denotes deletion. The numbers *c*, *x*, *y*, *a*, *b* are parameters.

## Generalization to matroids

The matroid function *f* is TG if:^{[1]}

- <math>\begin{align}

&f(M_1\oplus M_2) = f(M_1)f(M_2) \\ &f(M) = af(M/e) + b f(M \backslash e) \ \ \ \text{if } e \text{ is not coloop or bridge} \end{align}</math>

It can be shown that *f* is given by:

- <math>f(M) = a^{|E| - r(E)}b^{r(E)} T(M; x/a, y/b)</math>

where *E* is the edge set of *M*; *r* is the rank function; and

- <math>T(M; x, y) = \sum_{A \subset E(M)} (x-1)^{r(E)-r(A)} (y-1)^{|A|-r(A)}</math>

is the generalization of the Tutte polynomial to matroids.

## Grothendieck group

The invariant is named after Alexander Grothendieck because of a similar construction of the Grothendieck group used in the Riemann–Roch theorem. For more details see:

- W. T. Tutte, A ring in graph theory
- https://www.pdf-archive.com/2017/08/22/brylawski-1972-the-tutte-grothendieck-ring/

## References

- ↑
^{1.0}^{1.1}Welsh.*Complexity, Knots, Colourings and Counting*. - ↑
^{2.0}^{2.1}Goodall, Andrew. "Graph polynomials and Tutte-Grothendieck invariants: an application of elementary finite Fourier analysis". https://arxiv.org/pdf/0806.4848.pdf.