Lectures 19--21: The Tutte Polynomial Lectures 19-21: The Tutte Polynomial

Learning Outcomes

After these lectures you should be able to:

  1. calculate the Tutte Polynomial of graphs;
  2. prove that various graph invariants are evaluations of the Tutte Polynomial.

Recurrence Relation For the Tutte Polynomial

The Tutte Polynomial satisfies the following relations:
If G has no edges then
T(G;x,y) = 1.
If G has a bridge e then
T(G;x,y) = xT(G/e;x,y).
If G has a loop e then
T(G;x,y) = yT(G-e;x,y).
If G has an edge e that is neither a loop nor a bridge then
T(G;x,y) = T(G-e;x,y) + T(G/e;x,y).

Recipe Theorem

[The Recipe Theorem] Let f be a graph invariant satisfying the following recurrence relations:
If G has no edges then
f(G) = 1.
If G has a bridge e then
f(G) = xf(G/e).
If G has a loop e then
f(G) = yf(G-e).
If G has an edge e that is neither a loop nor a bridge then
f(G) = af(G-e) + bf(G/e).
Then
f(G) = a|E|-r(E)br(E) T æ
ç
è 		G; x
b
 , y
a
 ö
÷
ø 		.

Proofs that invariants are evaluations of the Tutte Polynomial

To show that an invariant is an evaluation of the Tutte Polynomial we show that it satisfies the same recurrence relations as T with particular values of x and y or show that it satisfies the conditions of the Recipe Theorem.

The number of forests of a graph G is given by T(G;2,1).

The number of forests of a graph with no edges is 1, that is just by taking the graph itself.

Now suppose we take a graph G with a bridge e. Each forest F of G/e corresponds to two forests of G because we can either just take F which is a forest of G or we can add e to F to get a forest of G. Hence the number of forests of G is twice the number of forests of G/e.

Now suppose we take a graph G with a loop e. Since e cannot be present in any forest we have that the number of forests of G is equal to the number of forests of G-e.

Finally let G contain an edge e that is neither a loop nor a bridge. A forest F may either contain e or it may not. If a forest does not contain e then it corresponds to a forest of G-e. Hence the number of forests of G not containing e is equal to the number of forests of G-e. A set F containing e is a forest in G if and only if F-e is a forest in G/e, hence the number of forests of G containing e equals the number of forests of G/e. Thus the number of forests of G equals the sum of the number of forests of G-e and the number of forests of G/e.

We have shown that the number of forests of a graph satisfies the recurrence relations for the Tutte polynomial with x = 2 and y = 1. Thus the number of forests is given by T(G;2,1).

Given a connected graph G, the reliability R(G;p) is given by
R(G;p) = (1-p)|E|-r(E)pr(E)  T æ
ç
è 		G;1, 1
1-p
 ö
÷
ø 		.

A connected graph G with no edges is just a single vertex which is always connected so R(G;p) = 1.

If G is a connected graph with a bridge e then G is connected if and only if e is present and G/e is connected. Hence
R(G;p) = pR(G/e;p).

If G is a connected graph with a loop e then G is connected whether or not e is present and so
R(G;p) = R(G-e;p).

Now let G be a connected graph with an edge e that is neither a loop nor a bridge then
R(G;p)
=
Pr
(G connected and e present)+ Pr
(G connected and e not present)
=
Pr
(G connected|e present) Pr
(e present) + Pr
(G connected|e not present) Pr
(e not present)
=
pR(G/e;p) + (1-p)R(G-e;p).
Thus we have shown that R satisfies the conditions of the Recipe Theorem with a = 1-p, b = p, x = p and y = 1. Hence
R(G;p) = (1-p)|E|-r(E)pr(E)  T æ
ç
è 		G;1, 1
1-p
 ö
÷
ø
as required.

File translated from TEX by TTH, version 2.61.
On 4 Jan 2001, 11:59.