Zeigen Sie mittels vollständiger Induktion über |E|, dass ∑v∈V deg(v) = 2|E| gilt.

Question

Frage:

Gegeben sei ein beliebiger ungerichteter Graph G = (V, E). Sei |V | = n.
(a) Zeigen Sie mittels vollständiger Induktion über |E|, dass ∑v∈V deg(v) = 2|E| gilt.
(b) Zeigen Sie, dass |E| ∈ O(n²) gilt.
(c) Zeigen Sie, dass mindestens zwei Knoten u, v ∈ V existieren, die denselben Knotengrad haben, wobei n ≥ 2 und u ungleich v gelten.
(d) Zeigen Sie, dass die Anzahl der Knoten mit ungeradem Knotengrad gerade ist.

Comments

Vom Duplikat:

Titel: vollständiger Induktion über |E|

Stichworte: induktion

Frage:

Gegeben sei ein beliebiger ungerichteter Graph G = (V, E). Sei |V | = n.
Zeigen Sie mittels vollständiger Induktion über |E|, dass ∑v∈V deg(v) = 2|E| gilt

Answer 1

(a) und (b) lassen sich mittels vollständiger Induktion zeigen.

(a) Betrachte im Induktionsschritt einen Graphen \(G=(V,E)\) mit \(|E|=m+1\) Kanten. Entferne nun eine Kante aus \(G\). Dann hast du ja wieder einen Graphen \(\tilde{G}\), wo nach Induktionsvoraussetzung bekannt ist, dass \(\sum\limits_{v\in \tilde{G}}=2(|E|-1)=2m\) gilt. Betrachte nun diejenigen Knoten, wo die Kante nach dem Entfernen jetzt fehlt. Was kannst du über deren Knotengrade aussagen?

(b) Zeige, dass ein ungerichteter Graph \(G=(V,E)\), bei dem jeder Knoten mit allen anderen genau einmal verbunden ist, genau \(|E|=\frac{n(n-1)}{2}=\frac{1}{2}(n^2-n)\) Kanten hat.

(c) Mache einen Widerspruchsbeweis. Nimm also an, dass für alle Knoten \(v_1,...,v_n\in V(G)\) mit \(v_i\neq v_j, i\neq j\) auch \(\deg(v_i)\neq \deg(v_j)\) gilt. Dann kannst du ja ohne Beschränkung der Allgemeinheit (O.B.d.A) annehmen, dass die Knoten so vorliegen, sodass \(0\leq \deg(v_1)<...<\deg(v_n)\) gilt. Dann gibt es auch für jeden Knoten \(v_i\in V(G)\) ein \(\alpha_i\in \mathbb{N}_{\geq 1}\), sodass

\(\deg(v_{i+1})=\deg(v_i)+\alpha_i>\deg(v_i),\quad i=1,...,n-1\) gilt. Nutze nun (b), um einen Widerspruch zu erzeugen.

(d) Benutze dafür Aussage (a).