Nachbarschafts-Training

Zeige, dass jeder endliche Graph eine bezüglich Inklusion maximale Menge paarweise kantenfremder Kanten besitzt.

Sei $M$ eine maximale Paarung in einem Graphen. Zeige, dass jede Kante mindestens einen Endpunkt besitzt, der zu einer Kante aus $M$ gehört.

Sei $S$ eine maximale unabhängige Knotenmenge. Zeige, dass jeder Knoten außerhalb von $S$ einen Nachbarn in $S$ besitzt.

Aus verschiedenen reellen Zahlen sollen genau $k$ ausgewählt werden, sodass ihre Summe maximal ist. Zeige, dass jede optimale Auswahl die $k$ größten Zahlen enthält.

Formuliere und beweise die entsprechende Aussage für eine Auswahl von $k$ Zahlen mit minimaler Summe.

Unter endlich vielen Intervallen wähle ein Intervall $I$ mit frühestem rechten Endpunkt. Zeige: Jede Familie paarweise disjunkter Intervalle, die ein anderes erstes Intervall $J$ benutzt, kann $J$ durch $I$ ersetzen, sofern $J$ ebenfalls den frühesten Startplatz der Familie belegt.

Erkläre anhand des Weges $1-2-3-4-5$, warum eine maximal unabhängige Menge nicht notwendig größtmöglich ist.

Formuliere eine Checkliste für Beweise mit gieriger Erweiterung oder Austauschverbesserung.