Beweisen Sie, dass es in jedem einfachen, ungerichteten, zusammenhängenden Graphen G

Question

Aufgabe:

Beweisen Sie, dass es in jedem einfachen, ungerichteten, zusammenhängenden Graphen \( G \) mit \( n \) Knoten einen Knoten gibt, dessen Abstand von allen anderen Knoten höchstens \( \frac{n}{2} \) ist.

Hinweis: Der Abstand zweier Knoten in \( G \) ist die Länge eines kürzesten Weges zwischen den Knoten.
(a) Beweisen Sie zunächst folgende Implikation: Gilt die obige Aussage für jeden Baum auf \( n \) Knoten, so gilt sie für jeden zusammenhängenden Graphen auf \( n \) Knoten.
(b) Komplettieren Sie den Beweis, indem Sie die Aussage für den Fall zeigen, dass \( G \) ein Baum ist.

Problem/Ansatz:

Kann mir wer dabei helfen oder sagen wo ich es naschauen soll

Answer 1

Hallo,

Für a): Jeder zusammenhängende Graph besitzt einen aufspannenden Baum. Dieser Baum besitzt eine Knoten mit der angegebenen Eigenschaft. Da der Graph mehr Wege hat als der Baum, können die Abstände von Knoten zu Knoten im Graphen höchstens kleiner sein als im Baum.

Zu b) Wähle einen längsten Weg in G, sagen wir \((x_0, \ldots,x_k,\ldots x_{2k})\). Dann hat \(x_k\) zu den Knoten im Weg einen Abstand von höchstens k. Wenn \(x_k\) mit einem weiteren Knoten verbunden wäre, sagen wir durch \((x_k,y_1, \ldots y_m)\), dann hätten wir einen Weg \((x_0, \ldots,x_k,y_1\ldots y_m)\) der Länge k+m. Weil der gewählte Weg die größte Länge hat, haben wir \(k+m \leq 2k\), also \(m \leq k \leq n/2\).

Jetzt musst Du nur noch überlegen, wie das ist wenn der längste Weg eine gerade Anzahl von Knoten hat.

Gruß Mathhilf