Beweis Graphentheorie Kantenmarkierung

Question

Aufgabe:

Sei G = (V,E) ein Graph, H⊂V eine echte Teilmenge der Knoten von G und K ein Kreis in G. Sei weiterhin eine Kantenmarkierung m: E→ℕ gegeben und es gelte für alle Kanten e∈E, dass m(e) = 1.

Beweise folgende Aussage: Die Summe der Kantenmarkierungen der Kanten von K, die einen Endknoten in H und einen Endknoten in V\H haben, ist gerade.

Kann mir jemand erklärend zeigen, wie man diese Aufgabe löst? Danke:)

Answer 1

Hallo,

definiere:

$$M:=\{(v,e) \in V \times K \mid v \in H, v \in e\}$$

D.h. in M liegen alle Paare (v,e), wobei v ein Knoten aus H auf der Kante e aus K ist. Da in einem Kreis jeder Knoten zu genau 2 Kanten gehört, ist die Anzahl von Paaren aus M gerade.

Wenn ich nun diese Paare abzähle, indem ich über die Kanten gehe, dann liefern die Kanten, die einen Knoten in H und einen nicht in H haben, den Beitrag 1. Die Anzahl dieser Kanten muss daher gerade sein.

Gruß Mahthhilf