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
