Graph/Baum/Charakterisierung/Fakt/Beweis/Aufgabe/Lösung

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.

Zur gelösten Aufgabe