Graphen/Ein-Punkt-Vereinigung/Aufspannende Bäume/Aufgabe

Aus Wikiversity

Es sei ein Graph zusammen mit zwei vollen Untergraphen mit (auf der Vertexmenge)

und derart, dass alle Kanten von entweder zu oder zu gehören. Zeige, dass die Anzahl der aufspannenden Bäume

von gleich dem Produkt der Anzahl der aufspannenden Bäume von und der Anzahl der aufspannenden Bäume von ist.