Grundlagen-Beweiswerkstatt

Skizziere mit einem kleinsten Gegenbeispiel den Beweis $1+2+\cdots+n=n(n+1)/2$ für alle positiven ganzen $n$.

Warum darf man aus der Annahme, dass es ein Gegenbeispiel mit positiver ganzzahliger Größe gibt, ein kleinstes Gegenbeispiel wählen?

In einem endlichen einfachen Graphen wähle einen Zyklus minimaler Länge. Zeige, dass zwischen zwei nicht aufeinanderfolgenden Zyklusknoten keine Kante liegen kann.

Beweise mit einem längsten Weg, dass jeder endliche Baum mit mindestens zwei Knoten ein Blatt besitzt.

Angenommen, positive ganze Zahlen $p,q$ mit $p^2=2q^2$ existieren. Zeige, dass daraus ein kleineres solches Paar entsteht und folgere einen Widerspruch.

Zeige, dass jeder endliche Graph eine maximale Menge paarweise nicht benachbarter Knoten besitzt.

Jemand wählt eine maximale unabhängige Knotenmenge und nennt sie automatisch größtmöglich. Erkläre den Fehler und gib ein Gegenbeispiel.

Formuliere eine universelle Prüfroutine für Extremalwiderspruch, kleinstes Gegenbeispiel und Reduktionsbeweis.