Kombinatorik-Beweiswerkstatt

Teile die Knoten eines endlichen Graphen so in $A,B$, dass möglichst viele Kanten zwischen den Teilen verlaufen. Zeige: Jeder Knoten hat mindestens so viele Nachbarn im anderen Teil wie im eigenen.

Zeige, dass jeder endliche Graph einen bipartiten Teilgraphen mit mindestens der Hälfte seiner Kanten besitzt.

Eine Knotenmenge $C$ berührt jede Kante und ist inklusionsminimal. Zeige: Für jedes $v\in C$ gibt es eine Kante, deren einziger Endpunkt in $C$ der Knoten $v$ ist.

In einer Paarung wechselt ein Weg abwechselnd zwischen ungewählten und gewählten Kanten und beginnt sowie endet an unbenutzten Knoten. Zeige, dass das Vertauschen der Kantenrollen eine größere Paarung liefert.

Folgere, dass eine Paarung größter Kardinalität keinen augmentierenden Weg besitzt.

Erkläre, warum beim maximalen Schnitt schon das Verbot jeder einzelnen Knotenverbesserung die in Aufgabe 1 benötigte Aussage liefert, aber nicht automatisch die exakte globale Schnittgröße bestimmt.

Erkläre, warum eine maximale Paarung augmentierende Wege der Länge 1 ausschließt, eine Maximum-Paarung aber augmentierende Wege jeder Länge.

Formuliere eine Entscheidungsroutine für maximale disjunkte Familien, minimale Überdeckungen, maximale Schnitte und Maximum-Paarungen.