Beweisen Sie: Hat jeder Knoten in einem Graphen einen Grad von mindestens 2, dann enthält der Graph einen Kreis.

Question

Aufgabe:

Beweisen Sie: Hat jeder Knoten in einem Graphen einen Grad von mindestens 2, dann enthält der Graph einen Kreis.

Problem/Ansatz:

Sei G=(V, E) ein Graph, für den gilt: ∀ v ∈ V: deg(v) = 2
⇒ Jeder Knoten hat 2 Kanten
⇒ |E| = 2 * |V|
Haben hier jede Kante doppelt gezählt
⇒ |E| = \( \frac{2 * |V|}{2} \) = |V|
Laut Definition gilt: E ⊆ {{x, y} : x, y ∈ V, x ≠ y }
⇒ |E| Kanten müssen |E| + 1 Knoten verbinden, damit der Graph kreisfrei bleibt
⇒ da der Graph nur |E| = |V| Knoten enthält, muss der Graph einen Kreis enthalten

Kann man diesen Beweis so führen?

Answer 1

Graph heisst G?

Dann englische Terminologie? https://en.wikipedia.org/wiki/Graph_theory

E ist die Menge der Kanten (edges, lines)

V ist die Menge der Knoten (vertices, nodes, points)

Elemente der entsprechenden Mengen: Kleinbuchstaben e und v.

Dein Ansatz:

Sei G=(V, E) ein Graph, für den gilt: ∀ v ∈ V: deg(v) = 2
Voraussetzung bedeutet nicht: Jeder Knoten hat mindestens 2 Kanten ⇒ |E| ≥ 2 * |V|
sondern 
|E| ≥ 2∗|V|/ 2 = |V| , da wir erst jede Kante doppelt gezählt haben.

Kann man diesen Beweis so führen?

Eher nicht.

Bisher hast du noch gar keinen Kreis, geschweige denn eine Definition von einem Kreis angegeben.

Daraus kannst du nichts folgern.

Die Folgerungspfeile, die ich bereits entfernt habe und die nun folgenden sind falsch.

Die Kantenmenge ist folgendermassen definiert: E ⊆ {{x, y} : x, y ∈ V, x ≠ y }
⇒ |E| Kanten müssen |E| + 1 Knoten verbinden, damit der Graph kreisfrei bleibt
⇒ da der Graph nur |E| = |V| Knoten enthält, muss der Graph einen Kreis enthalten