Spannbaum-Training

Zeige: Entfernt man aus einem Zyklus eines zusammenhängenden Graphen eine Kante, bleibt der Graph zusammenhängend.

Entferne wiederholt Zykluskanten und zeige die Aussage.

Zeige, dass ein bezüglich Kantenanzahl minimaler zusammenhängender Spannteilgraph ein Baum ist.

Sei $T$ ein Baum und $e=uv$ eine neue Kante. Zeige, dass $T+e$ genau einen Zyklus besitzt.

In einem minimal gewichteten Spannbaum wird eine Nichtbaumkante $e$ ergänzt. Zeige: Keine Kante des entstehenden Zyklus darf schwerer als $e$ sein.

Ein Schnitt teilt die Knoten in zwei nichtleere Teile. Zeige, dass eine eindeutig leichteste Schnittkante in jedem minimalen Spannbaum liegen muss.

Was folgt ohne Eindeutigkeit für eine leichteste Schnittkante?

Formuliere die Prüfschritte für Reduktion und gewichteten Kantentausch.