Zeigen Sie die Äquivalenz folgender Aussagen:

Question

Aufgabe:

Gegeben sei ein Graph G = (V, E) mit |V | ≥ 2 Knoten. Zeigen Sie die Äquivalenz folgender Aussagen:
i) Zwischen zwei beliebigen Knoten vi, Vj ∈ V existiert genau ein Pfad.
ii) G ist ein Baum.

Problem/Ansatz:

Ich weiß leider nicht, wie die Aufgabe gelöst wird... für Hilfe wäre ich dankbar

Answer 1

Mach dir erstmal klar, was ein Baum ist: Ein zusammenhängender ungerichteter Graph ist ein Baum, wenn er keine Kreise enthält.

Zu i) => ii). Das kannst du mit einem Widerspruch machen. Nimm an, dass dein Graph mindestens ein Kreis enthält und führe das mit i) zu einem Widerspruch.

Zu ii) => i). Das kannst du auch per Widerspruch zeigen. Angenommen, es gäbe für mindestens zwei Knoten mehr als einen Pfad. Was kannst du daraus schließen?