Ungerichteter Graph/Bäume und Wälder/Textabschnitt

Definition

Ein Graph ohne Kreis heißt Wald

Definition

Ein zusammenhängender Wald heißt Baum.

Lemma

Es sei ${}G$ ein Baum mit zumindest zwei Knotenpunkten.

Dann besitzt ${}G$ ein Blatt.

Beweis

Wir betrachten die Menge aller Wege ohne Kantenwiederholungen. Da es in ${}G$ keine Kreise gibt, gibt es in einem solchen Weg auch keine Knotenwiederholung. Somit haben alle diese Wege eine (durch ${}{\#\left(V\right)}$) beschränkte Länge. Wir betrachten einen Weg, der unter diesen Wegen in ${}G$ maximale Länge besitzt. Dann sind die Endpunkte Blätter, da man andernfalls den Weg verlängern könnte.

$\Box$

Lemma

Es sei ${}G=(V,E)$ ein Graph und ${}b\in V$ ein Blatt des Graphen.

Dann ist ${}G$ genau dann ein Baum, wenn ${}G\setminus b$ ebenfalls ein Baum ist.

Beweis

Die Äquivalenz der Zusammenhangseigenschaft folgt aus Fakt. Ein Kreis in ${}G\setminus b$ ist direkt ein Kreis in ${}G$. Die Umkehrung folgt aus Fakt.

$\Box$

Satz

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$.

Beweis

Aus (1) folgt (2). Da ${}G$ nach Voraussetzung zusammenhängend ist, gibt es zu ${}u,v$ zumindest einen verbindenden Weg. Würde es zwei Wege geben, so könnte man daraus direkt einen Zyklus und dann auch einen Kreis konstruieren, was ausgeschlossen ist.

Aus (2) folgt (1). Die Zusammenhangseigenschaft ist klar. Würde es einen Kreis geben, so könnte man dies direkt als einen zweifachen Weg ohne Wiederholung zwischen zwei Punkten auffassen.

Aus (1) folgt (3). Wir führen Induktion über die Anzahl der Punkte von ${}G$. Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Es sei also ${}G$ ein Baum mit ${}n\geq 2$ Punkten. Nach Fakt besitzt ${}G$ ein Blatt und nach Fakt ist ${}G\setminus b$ ebenfalls ein Baum. Dabei wird ein Punkt und eine Kante herausgenommen. Nach Induktionsvoraussetzung gilt die Gleichung für den verkleinerten Baum, also gilt sie auch für ${}G$.

Von (3) nach (1). Wir führen wieder Induktion über die Knotenanzahl, bei einem Knoten ist alles klar. Aufgrund der Voraussetzung und Fakt gilt

${}\sum _{v\in V}d(v)=2\cdot {\left({\#\left(V\right)}-1\right)}=2{\#\left(V\right)}-2\,.$

Wegen der Zusammenhangseigenschaft sind die Grade zumindest ${}1$. Deshalb muss es (zumindest ${}2$) Punkte mit Grad ${}1$, also Blätter geben. Es sei ${}b$ ein Blatt. Die Formel gilt dann auch für ${}G\setminus b$. Nach Induktionsvoraussetzung ist ${}G\setminus b$ ein Baum, und daher ist nach Fakt auch ${}G$ ein Baum.

$\Box$