Graph/Baum/Charakterisierung/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Charakterisierungssatz für Bäume

Es sei ein Graph mit nichtleerer Knotenmenge . Dann sind folgende Aussagen äquivalent.

  1. ist ein Baum.
  2. Zwischen je zwei Punkten gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
  3. ist zusammenhängend und es gilt .
Zum Beweis, Alternativen Beweis erstellen