Handouts
 The book
“Random Walks and Electrical Networks”
by Doyle and Snell
is available for free from
Peter Doyle's homepage.

The book
“Probability on Trees and Networks”
by Lyons and Peres covers many topics
related to this course. Chapter 4 contains an excellent discussion
of random spanning trees, Wilson's algorithm for sampling them,
and connections between random spanning trees, electrical networks,
and determinants.

If you want to understand some more about the combinatorics
underlying Kirchhoff's matrixtree theorem, the paper
Chipfiring games, potential theory on graphs, and spanning trees
by Baker and Shokrieh is an excellent place to start. They give
an “efficient bijective” proof of the theorem.

A different combinatorial proof of Kirchhoff's Theorem,
working directly with the definition of the determinant
as a sum over permutations, can be found in
these lecture notes by Lionel Levine.

A different proof of Kirchhoff's Theorem, using the CauchyBinet
formula, is presented in
Chapter 9 of Richard Stanley's course notes for
Algebraic Combinatorics.

Yet another proof of Kirchhoff's Theorem, using an algebraic fact
that looks similar to CauchyBinet but is slightly different, is in
these lecture notes by Nikhil Srivasatava.

Lecture notes on Cheeger's Inequality
by Dan Spielman.

We will be discussing Spielman and Teng's paper
Spectral partitioning works: Planar graphs and finite element meshes
(Linear Algebra and its Applications 421 (23), 2007, original
version appeared in FOCS 1996).

We will also be discussing the planar separator theorem of Lipton and
Tarjan.
These notes by Jeff Erickson contain
an elementary proof due to Alon, Seymour, and Thomas, as well as a
proof based on circle packing due to Spielman and Teng. The
circle packing proof depends on a nontrivial result by Miller, Teng,
Thurston, and Vavasis from their paper
Separators for spherepackings and nearest neighbor graphs
(J. ACM 44(1), 1997).