Graph/Baum/Charakterisierung/Fakt

Charakterisierungssatz für Bäume

Es sei ${}G=(V,E)$ ein Graph mit nichtleerer Knotenmenge ${}V$. Dann sind folgende Aussagen äquivalent.

1. ${}G$ ist ein Baum.
2. Zwischen je zwei Punkten ${}u,v\in V$ gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
3. ${}G$ ist zusammenhängend und es gilt ${}{\#\left(E\right)}={\#\left(V\right)}-1$.

Zum Beweis, Alternativen Beweis erstellen