Knotengrade - Kanten - Knoten

Question

Aufgabe:

Knotengrade

Problem/Ansatz:

1) Zeigen Sie, dass jeder einfache ungerichtete Graph mit mehr als einem Knoten zwei Knoten mit dem gleichen Grad enthält.
Hinweis: Betrachten Sie eine Zusammenhangskomponente mit mehr als zwei Knoten (existiert
diese?). Leiten Sie eine obere und untere Schranke für deren Knotengrade her. Vergleichen Sie die
Anzahl der Knoten mit der Anzahl der möglichen Werte für die Knotengrade.

2) Zeigen Sie, dass jeder Baum G= (V,E) mit |V| ≥ 2 mindestens zwei Knoten vom Grad eins
enthält.
Hinweis: Leiten Sie einen Widerspruch mit Hilfe der Lemmas.

Comments

Was ist denn eine untere Schranke für den Knotengrad in einem zusammenhängenden Graph? Was ist die obere Schranke , in jedem Graph?

---

Ich muss bei die erste zeigen , ist mir leider nicht klar

---

Wie ist denn Knotengrad definiert?

Kann der Knotengrad den Wert 0 annehmen, den Wert 1?

Wenn ich n Knoten habe, kann der Knotengrad den Wert n oder n+1 annehmen?

---

Der Knotengrad eines Knotens in einem Graphen ist die Anzahl der Kanten, die mit diesem Knoten verbunden sind.
Ein Knoten im Graph kann einen Knotengrad von 0 haben, wenn er keine Kanten zu anderen Knoten hat
Ein Knoten im Graph kann auch einen Knotengrad von 1 haben, wenn er nur mit einem anderen Knoten durch eine Kante verbunden ist.
Für einen ungerichteten Graphen mit n Knoten kann der Knotengrad maximal (n-1) betragen, da jeder Knoten mit allen anderen Knoten außer sich selbst verbunden sein kann. Also nicht n+1

Answer 1

Folgende Fälle

1. Alle Knoten haben den Grad 0. Aussage ist trivial richtig

2. Es gibt nur Zusammenhangskomponten mit jeweils 2 Knoten. Diese haben dann den Grad 1. Aussage erfüllt.

3. Es gibt eine Zusammenhangskomponente mit n Knoten, die Knotenteilmenge sei \(V'\), dann ist

$$d:V' \to \{1,2, \ldots n-1\}$$

eine Abbildung von eine Menge mit n Elementen in eine Menge mit n-1 Elementen. Eine solche Abbildung ist nicht injektiv (Schubfachprinzip). Es gibt also \(v,w \in V'\) mit \(d(v)=d(w)\)

Comments

Für die (2) zweite teil Aufgabe:

Um zu zeigen, dass jeder Baum = (, ) mit || ≥ 2 mindestens zwei Knoten vom Grad eins enthält, können wir einen Beweis durch Widerspruch verwenden.

Annahme: enthält höchstens einen Knoten vom Grad eins.

Dann muss jeder andere Knoten in mindestens Grad zwei haben, da ein Baum ist und daher zusammenhängend und kreisfrei ist.

Aber dann gilt:

\( \sum\limits_{v∈V} \) d(v) ≥ 2 |V|

Dies folgt aus der Tatsache, dass jeder Knoten mindestens Grad zwei hat und es mindestens zwei Knoten gibt (einer mit Grad eins und einer mit Grad mindestens zwei).


Ist meine Lösung richtig ?

---

Ich sehe Dein Argument noch nicht ganz. Ich denke, Du musst die Info verwenden, dass im Baum \(|E|=|V|-1\) ist. Dann mit Deiner Überlegung, falls es nur einen Knoten mit Grad 1 gibt:

$$2(|V|-1)=\sum_{v \in V}d(v) \geq 1+2(|V|-1)=2|V|-1$$

Widerspruch!

---

Nun können wir diese Aussage mathematisch mit Hilfe der Formel |E| = |V| - 1 beweisen. Wir wissen, dass jeder Baum mindestens ein Blatt hat, d.h. einen Knoten vom Grad eins. Angenommen, es gibt nur einen Knoten vom Grad eins. Dann hat dieser Knoten keine weiteren Nachbarn und es gibt keinen Weg, um einen weiteren Knoten zum Baum hinzuzufügen. Daher hätte der Baum nur einen Knoten und keine Kanten, was der Bedingung |E| = |V| - 1 widerspricht.

Daher muss jeder Baum mit |V| ≥ 2 mindestens zwei Knoten vom Grad eins enthalten, wie zu zeigen war.

Wie sieht es aus ?

---

und es gibt keinen Weg, um einen weiteren Knoten zum Baum hinzuzufügen.

Das verstehe ich nicht

---

das bedeutet das der Knote nur 1 Nachbar hat

---

Angenommen, x ist der einzige Knoten mit Grad 1. Dann hat er einen Nachbarn y. Dieser Nachbar kann doch weitere Nachbarn haben .....

---

Nun können wir diese Aussage mathematisch mit Hilfe der Formel |E| = |V| - 1 beweisen. Wir wissen, dass jeder Baum mindestens ein Blatt hat, d.h. einen Knoten vom Grad 1.

Angenommen, x ist der einzige Knoten mit Grad 1. Dann hat er einen Nachbarn y
dieser Nachbar kann doch weitere Nachbarn haben. Daher hätte der Baum nur einen Knoten und keine Kanten, was der Bedingung |E| = |V| - 1 widerspricht.

Daher muss jeder Baum mit |V| ≥ 2 mindestens zwei Knoten vom Grad eins enthalten, wie zu zeigen war.

---

Ich glaube so meinen Sie . Vielen Dank für Ihre Hilfe und Ihre Aufmerksam