# 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.