Matrix-Gerüst-Satz, matrix tree theorem, eine Formel, die für einen markierten Graphen die Anzahl seiner verschiedenen spannenden Bäume angibt.

Es sei A = (a_ij) die Adjazenzmatrix eines Graphen G mit der Eckenmenge E(G) = {x₁, x₂, …, x_n} und d(x_i) der Grad der Ecke x_i für i = 1, 2, …, n. Ersetzt man in −A die Elemente −a_ij = 0 durch d(x_i) für alle 1 ≤ i ≤ n, so entsteht daraus die sogenannte Admittanzmatrix B von G. Streicht man in der Admittanzmatrix B die i-te Zeile sowie die i-te Spalte für ein 1 ≤ i ≤ n, und bestimmt von dieser so entstandenen ((n − 1) × (n − 1))-Matrix B_i die Determinante, so erhält man die Anzahl der spannenden Bäume von G. Insbesondere ist det B_i unabhängig von i.

Dieser sogenannte Matrix-Baum-Satz findet sich der Idee nach bereits in einer Arbeit von G.R. Kirchhoff aus dem Jahre 1847. Ein klarer, auf dem Determinantensatz von Cauchy-Binet beruhender Beweis wurde 1954 von H. Trent gegeben. Als Spezialfall erhält man daraus, daß der vollständige Graph K_n genau nⁿ⁻² verschiedene spannende Bäume besitzt. Diese Anzahlformel wurde bereits 1889 von A. Cayley bewiesen.