Ungerichteter Graph/Spannbäume/Kirchhoff/Fakt

Satz von Kirchhoff

Es sei ${}G$ ein Multigraph und sei ${}L$ die Laplace-Matrix zu ${}G$. Es sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von ${}G$ gleich der Determinante von ${}L'$.

Zum Beweis, Alternativen Beweis erstellen