Lokale Verbesserungen

Zeige: In einem endlichen Graphen liegen alle Nachbarn eines Endpunkts eines längsten einfachen Weges auf diesem Weg.

Sei $I$ eine inklusionsmaximale unabhängige Knotenmenge eines endlichen Graphen. Zeige, dass jeder Knoten außerhalb von $I$ einen Nachbarn in $I$ besitzt.

Zeige: Jeder endliche Graph besitzt einen Schnitt mit mindestens der Hälfte seiner Kanten.

Aus einer endlichen Familie nichtleerer Mengen wird eine inklusionsmaximale paarweise disjunkte Teilfamilie gewählt. Zeige, dass jede ursprüngliche Menge eine gewählte Menge schneidet.