Beweiswerkstatt

Zeige per Induktion, dass ein Baum mit $n$ Knoten $n-1$ Kanten hat.

Zeige per Induktion, dass jeder Baum mit zwei Farben korrekt knotengefärbt werden kann.

Warum endet das Tauschen benachbarter Inversionen?

Verschiebe einen Knoten, wenn er mehr Nachbarn auf seiner Seite als gegenüber hat. Zeige Terminierung.

Erkläre die logische Äquivalenz beider Stile bei einer Reduktion um ein Extremobjekt.

Gib ein allgemeines Schema für Invariante plus Extremalzug plus Monovariniante.

Eine Lösung nennt eine größte Zahl und eine fallende Summe, zeigt aber nicht, dass an der größten Zahl ein legaler Zug existiert. Warum ist sie unvollständig?

Formuliere eine universelle Checkliste für Extremal-Methodenketten.