Brücke bei geraden Knoten

Question

Hallo ich habe folgende Aufgabe:

Eine Brücke in einem zusammenhängenden Graphen \(G = (V, E)\) ist eine Kante \(e\in E\), so dass der Graph \((V, E\setminus \{e\})\) nicht mehr zusammenhängend ist. Beweise oder widerlege die Aussage, dass ein Graph, in dem alle Knoten geraden Grad haben, keine Brücke enthält.

Ich habe leider keine Ahnung wie ich den Beweis bzw. den Widerleg zeigen soll.

Danke schonmal für die Hilfe :)

Answer 1

Hallo,

es sei \(\deg(v)\) der Grad eines Knotens \(v\) und definitionsgemäß die Anzahl der Kanten an diesem Knoten \(v\). Dann ist die Summe aller Grade aller Knoten (auf jede Kante kommen zwei Knoten) $$\sum_{v \in V} \deg(v) = 2|E|$$wobei \(|E|\) die Anzahl der Kanten des Graphen ist.

Daraus folgt wiederum, dass die Anzahl der ungeraden Knoten in jedem Graphen gerade sein muss. Liegt ein Graph vor, nur mit Knoten von geradem Grad, so würden nach dem Entfernen einer Kante die beiden beteiligten Knoten ungerade. Würde daraufhin der Graph in zwei Untergraphen zerfallen, so würde jeder der beiden Untergraphen nur genau einen ungeraden Knoten haben.

Und das ist nach der Überlegung oben nicht möglich. Folglich gibt es keine Brücke in einem Graphen aus Knoten mit geradem Grad.

Gehen beide Enden der entfernten Kante zum identischen Knoten, so bleibt der Graph natürlich auch ganz. Diese Kante kann also auch keine Brücke sein.

Gruß Werner