Graphstruktur-Training

Sei $v_0\ldots v_k$ ein längster Weg in einem endlichen Graphen. Zeige, dass jeder Nachbar von $v_0$ bereits auf dem Weg liegt.

Zeige, dass jeder endliche Baum mit mindestens zwei Knoten mindestens zwei Blätter besitzt.

Zeige, dass ein kürzester Zyklus in einem endlichen einfachen Graphen keine Sehne besitzt.

Ein Graph besitzt einen Zyklus der Länge 4, dessen gegenüberliegende Knoten verbunden sind. Zeige, dass er einen kürzeren Zyklus besitzt.

Ein Graph hat $n$ Knoten und $m$ Kanten. Zeige, dass ein Knoten Grad mindestens $2m/n$ besitzt.

Zeige, dass jeder Knoten außerhalb eines längsten Weges nur mit inneren Wegknoten verbunden sein kann, nicht mit dessen Endpunkten.

Zeige, dass ein kürzester ungerader Zyklus keine Sehne haben kann, die ihn in einen geraden und einen ungeraden Zyklus zerlegt.

Formuliere eine Checkliste für längste Wege, kürzeste Zyklen und extreme Grade.