Graph/Paarungen/Symmetrische Differenz/Fakt/Beweis

Beweis

Ein jeder Knotenpunkt liegt höchstens an einer Kante aus an, da ja sonst wäre, was der Paarungseigenschaft widerspricht. Gleiches gilt für . Da die Kanten in durch gegeben sind, besitzt jeder Knotenpunkt in höchstens zwei anliegende Kanten, wobei bei zwei Kanten die eine aus und die andere aus sein muss. Deshalb verbleiben die angegebenen Möglichkeiten.