ICS Theory Group

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.