Graph/Paarungen/Symmetrische Differenz/Fakt/Beweis

Beweis

Ein jeder Knotenpunkt ${}v\in V$ liegt höchstens an einer Kante aus ${}P\setminus Q$ an, da ja sonst ${}\{v,u\},\{v,w\}\in P$ wäre, was der Paarungseigenschaft widerspricht. Gleiches gilt für ${}Q\setminus P$. Da die Kanten in ${}H$ durch ${}(P\setminus Q)\cup (Q\setminus P)$ gegeben sind, besitzt jeder Knotenpunkt in ${}H$ höchstens zwei anliegende Kanten, wobei bei zwei Kanten die eine aus ${}P$ und die andere aus ${}Q$ sein muss. Deshalb verbleiben die angegebenen Möglichkeiten.

Zur bewiesenen Aussage