Graphentheorie: Beweisen oder widerlegen: Graph, in dem alle Knoten geraden Grad haben, enthält keine Brücke.

Question

Aufgabe:

Sei G = (V,E) ein Graph. Eine Kante e ∈ E heißt Brücke, wenn der Graph G0 = (V,E \{e}) mehr Zusammenhangskomponenten als G hat. Beweisen oder widerlegen Sie: Ein Graph, in dem alle Knoten geraden Grad haben, enthält keine Brücke.

Problem/Ansatz:

Kann mir jemand bei dieser Aufgabe eventuell Helfen?

Comments

Vom Duplikat:

Titel: Beweisen oder widerlegen: Ein Graph in dem alle Knoten geraden Grad haben, enthält keine Brücken.

Stichworte: brücke,knoten,komponenten,graph,graphentheorie

Sei G=(V,E) ein Graph. Die Kante e Element E heisst Brücke, ....

Ein Graph in dem alle Knoten geraden Grad haben, enthält keine Brücken.

Kann mir jemand helfen ? Ich komme nicht mal auf ein Ansatz!

Hilfe !

Answer 1

Die Summe der Grade aller Knoten ist gerade, weil jede Kante zu genau zwei Knoten gehört.

Also gibt es keinen Graphen, der genau einen Knoten mit ungeradem Grad hat.

Entfernt man aus einem Graphen, in dem alle Knoten geraden Grad haben, eine Kante, dann kann keine neue Zusammenhangskomponente entstanden sein, weil in ihr genau ein Knoten ungeraden Grad hätte.

Comments

vielen Dank :)