Gerüste, Satz von Cayley

1. Gerüst:

Ein Baum, der Teilgraph eines ungerichteten Graphen G ist, wird ein Gerüst von G genannt. Jeder zusammenhängende endliche Graph G enthält ein Gerüst H:
Enthält G einen Kreis, dann löscht man in G eine Kante dieses Kreises. Der entstandene Graph G₁ ist wieder zusammenhängend und kann durch Löschen einer Kante eines Kreises von falls eine solche existiert, in einen zusammenhängenden Graphen G₂ überführt werden. Nach endlich vielen Schritten erhält man ein Gerüst von

Beispiel

Die rechte Abbildung zeigt ein Gerüst H des in der linken Abbildung dargestellten Graphen

2. Satz von Cayley:

Jeder vollständige Graph mit n Knoten (n>1) hat genau n^n-2 Gerüste.