Bipartite Graphen

Gradparität, Schnitte und bipartite Wege · Abschnitt 43 von 64

Beweis

Bipartite Graphen

Graphinvarianten entstehen durch Doppelzählung und Klassenwechsel: Jede Kante wird genau zweimal in Graden und genau einmal beim Überqueren eines gewählten Schnitts sichtbar.

Checkliste

Struktur-Audit

Welche lokale Einheit wird gezählt oder bewegt?
Welche globale Größe bleibt unter jeder Operation erhalten?
Sind Richtung, Markierung und Voraussetzungen korrekt?
Ist die Folgerung nur notwendig oder auch konstruktiv hinreichend?