Bäumen und Teilgraphen..

Question

Aufgabe:

Sei T ein Baum und T_i   ,i = 1,..,k, Teilgraphen von T, die selbst wieder Bäume sind.
Für den Schnitt der Knotenmengen gelte

V' := ( ⋂_{i=1} ) ^k V(T_i ) ≠ ∅

Problem:
Zeige, dass dann der induzierte Teilgraph T' := T[V'] wieder ein Baum ist.

Answer 1

Weil T' ein Teilgraph von T ist, ist er kreisfrei.

Seien nun \(v,w \in V'\). Dann ist zu zeigen, dass sie in T' durch einen Weg verbunden sind.

Zunächst existiert ein Weg \((v=x_0,x_1, \ldots, x_n=w)\) in \(T_1\). Wir zeigen, dass dieser Weg in allen anderen \(T_i\) liegt. Wenn er nicht, sagen wir, in \(T_2\) liegt, dann existiert dort ein Weg \((v=y_0,y_1, \ldots y_m=w)\), der verschieden ist von dem Weg in \(T_1\).

Also gibt es einen kleinsten Index i mit \(x_i=y_i\) und \(x_{i+1} \neq y_{i+1}\) (Also der erste Knoten, nachdem sich die beiden Wege trennen, das kann - muss aber nicht - schon v sein.). Dann existiert ein kleinster Index k>i, dazu j>i mit \(x_k=y_j\) (Also der Knoten, wo beide Weg zum ersten mal wieder zusammentreffen, spätesten bei w).

Damit hätten wir in T einen Kreis konstruiert: $$(y_i=x_i,x_{i+1}, \dots,x_{k-1},x_k=y_j,y_{j-1}, \dots y_j)$$

T enthält aber keinen Kreis.