Kirchhoffs træ sætning

Kirchhoffs træ sætning, opkaldt efter Gustav Kirchhoff, er en meget anvendt sætning indenfor det matematiske område grafteori. Sætningen omhandler antallet af udspændende træer i en graf. Nogle sætninger som følger af Kirchhoffs træ sætning er Cayleys formel, som omhandler antallet af udspændende træer i komplette grafer, samt Scoins formel som omhandler antallet af udspændende træer i de komplette todelte grafer.

Kirchoffs træ sætning

Lad $K$ være konduktansmatricen for en sammenhængende graf $\Gamma$ og lad $K_i$ være den matrix, der fås af $K$ ved at man sletter række $i$ og søjle $i$. Da er

$det(K_i)=\tau(\Gamma) \,$,

hvor $\tau(\Gamma)$ er antallet af udspændende træer i $\Gamma$.