Counting the Number of Spanning Trees in a Graph

print

Speaker: 

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

Time: 

Friday, 13 November 2009 (All day)

Venue: 

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