ICS 269, Winter 1996: Theory Seminar
5 January 1996:
The Parity of the Number of Spanning Trees in a Graph
David Eppstein, ICS, UC Irvine
Every bipartite Eulerian graph has an even number of spanning
trees. More generally, a graph has evenly many spanning trees if
and only if it has an Eulerian edge cut, and if B is any edge cut
in a graph G, the gcd of vertex degrees in B divides the number of
spanning trees of G. The proofs of these facts are based on a new
algebraic characterization of the number of spanning trees of G,
due to
Bacher, de la Harpe, and Nagnibeda.