Lesson 4

Theorem (Cayley, 1889). Let \(G\) be a graph that may have multiple edges and loops, and let \(e\) be an edge of \(G\) that is not a loop. Then \[\tau(G)=\tau(G \setminus e) + \tau(G / e) \ .\]

Proof. The first term accounts for all trees that do not contain the edge \(e\). The second term accounts for all trees that contain edge \(e\): there is a natural bijection between such trees and the spanning trees of the graph \(G / e\) (contracting or expanding an edge preserves the tree structure).◼

The base case of this recurrence relation is as follows: graphs \(G\) where all edges are loops. If the graph has more than one vertex, it is disconnected, hence \(\tau(G)=0\); if there is only one vertex, then \(\tau(G)=1\).

Using this recurrence relation, one can compute \(\tau(G)\). However, in the general case, implementing such a computation leads to an exponential number of recursive calls.