Graphentheorie: Äquivalenz zusammenhängender Graphen

Question

Aufgabe:

Eine Kante K in einem zusammenhängenden Graphen ist eine Brücke, falls nach dem Entfernen von K der Graph nicht mehr zusammenhängend ist. Zeigen Sie, dass folgende Aussage über einen zusammenhängenden Graphen G äquivalent sind:

1. G ist eine Laterne.
2. Jede Kante von G ist eine Brücke.

Problem/Ansatz:

Komme leider nicht weiter. Ich Bitte um Hilfe :)

Comments

Was ist eine Laterne?
"Komme nicht weiter" heißt, Du hast angefangen. Was hast Du Dir also schon überlegt?

---

Ups das Wort Laterne hab ich von einer anderen Aufgabe. Es muss "G ist ein Baum" heißen. Mein Fehler.

Ein Baum ist ein minimaler zusammenhängender Graph. Wenn man eine Kante entfernst, ist der Graph nicht mehr zusammenhängend. Das bedeutet, jede Kante ist eine Brücke.
Ein Graph, bei dem jede Kante eine Brücke ist, kann keine Zyklen enthalten. Denn wenn es Zyklen gäbe, könnte man eine Kante im Zyklus entfernen, ohne den Graphen in zwei Teile zu zerlegen. Das widerspricht der Annahme, dass jede Kante eine Brücke ist. Zusammen mit der Bedingung, dass der Graph zusammenhängend ist, ergibt das, dass der Graph ein Baum sein muss.

Ich weiß aber nicht, wie ich die nun "beweisen" kann. Aber das war jetzt z.B. mein Gedanke dahinter.

Answer 1

Da hast Du doch ein paar gute Gedanken. Bitte gleich mitliefern, damit man weiß wie man gezielt helfen kann.

So wie ich das sehe, ist die Bedingung 2. äquivalent zu "minimal zusammenhängend", und damit zu "Baum".

Wenn in der Vorlesung der Satz da war (oder als Def.), dass Baum äquivalent zu min. zushgd ist, dann ist fast nichts zu zeigen (nur dass 2. äquiv. zu min. zushgd ist, aber das ist eigentlich ja die Def.).

Es hängt also davon ab, wie in der Vorlesung ein "Baum" definiert ist und welche Resultate bekannt sind, die dazu äquivalent sind.

Comments

Hab tatsächlich nur diese Definition gefunden: Ein Graph, in dem beliebige Ecken A ≠ B durch einen Weg verbunden sind, heißt zusammenhängend. Ein zusammenhängender Graph ohne Kreise heißt Baum (insbesondere gibt es in Bäumen auch keine Schlingen).

---

Habs hinbekommen. Vielen dank!