Graph/Paarungen/Symmetrische Differenz/Fakt

Es sei ${}G=(V,E)$ ein Graph und seien ${}P$ und ${}Q$ Paarungen in ${}G$. Es sei ${}H$ derjenige Graph auf ${}V$, dessen Kantenmenge die symmetrische Differenz von ${}P$ und ${}Q$ ist.

Dann sind die Zusammenhangskomponenten von ${}H$ von einer der folgenden Gestalt.

1. Ein isolierter Punkt.
2. Ein linearer Graph, wobei die Kanten abwechselnd zu ${}P$ bzw. zu ${}Q$ gehören.
3. Ein Rundgang mit gerader Länge, wobei die Kanten abwechselnd zu ${}P$ bzw. zu ${}Q$ gehören.

Zum Beweis, Alternativen Beweis erstellen