Aufgabe: Graphentheorie beweise
Text erkannt:
E 3.2 Für einen Graphen \( G=(V, E) \) ist der maximale Knotengrad \( \Delta(G) \) von \( G \) definiert als
\( \Delta(G):=\max _{v \in V} \operatorname{deg}_{G}(v) \)
und der minimale Knotengrad \( \delta(G) \) von \( G \) als
\( \delta:=\min _{v \in V} \operatorname{deg}_{G}(v) . \)
Zeigen oder widerlegen Sie jeweils, dass für jeden zusammenhängenden Graphen \( G=(V, E) \) mit \( |V| \geq 2 \) gilt:
(a) Es gibt einen aufspannenden Baum \( T=\left(V, E^{\prime}\right) \) von \( G \), der einen Knoten \( w \in V \)
(b) Jeder aufspannende Baum \( T=\left(V, E^{\prime}\right) \) von \( G \) enthält einen Knoten \( w \in V \) vom \( \operatorname{Grad} \operatorname{deg}_{T}(w)=\Delta(G) \).
\( -2- \)
(c) Es gibt einen aufspannenden Baum \( T=\left(V, E^{\prime}\right) \) von \( G \), der einen Knoten \( w \in V \)
(d) Es gibt einen aufspannenden Baum \( T=\left(V, E^{\prime}\right) \) von \( G \), der einen Knoten \( w \in V \)
(e) Es gibt einen aufspannenden Baum \( T=\left(V, E^{\prime}\right) \) von \( G \), der zwei Knoten \( w_{1}, w_{2} \in V \) vom \( \operatorname{Grad} \operatorname{deg}_{T}\left(w_{1}\right)=\operatorname{deg}_{T}\left(w_{2}\right)=\delta(G) \) enthält.
Problem/Ansatz: Kann mir jemand bei diesen Aufgaben helfen. Ich weiß leider keinen Lösungsansatz.
