0 Daumen
2,3k Aufrufe

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?

Avatar von

1 Antwort

0 Daumen

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
Avatar von 162 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community