Counting the Number of Spanning Trees in a Graph


Rakesh Venkat School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road <b


Friday, 13 November 2009 (All day)


  • A-212 (STCS Seminar Room)

A classic counting algorithm, Kirchhoff's theorem gives a formula for finding the number of spanning trees in a simple, connected, undirected graph. I will discuss a simple proof of this theorem, based on elementary linear algebra.