TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 300

Aus VoWi
Zur Navigation springen Zur Suche springen

Sei G ein einfacher Graph. Man zeige, dass dann die Anzahl der Knoten ungeraden Grades gerade ist.

Hilfreiches[Bearbeiten]

Handschlaglemma
Handschlaglemma[Bearbeiten, WP, 2.13 Satz]

In einem einfachen Graphen G gilt: \sum_{v\in V(G)} d(v) = 2\cdot |E(G)| Die Summe der Knotengrade ist genau doppelt so groß wie die Anzahl der Kanten. E(G) ist die Menge der Kanten, V(G) die Menge der Knoten des Graphen G.

Lösung[Bearbeiten]

Aus dem Handschlaglemma ist ersichtlich, dass die Summe der Knotengrade gerade sein muss, da diese als das Doppelte der Kantenanzahl dargestellt werden kann.

Außerdem kann ein Knotengrad entweder gerade sein oder nicht, die (gerade) Summe der Knotengrade setzt sich also zusammen aus der Summe der Knoten mit geradem Knotengrad und der Summe der Knoten mit ungeraden Knotengrad. Formal:

\sum_{v \in V(G)} d(v) = \sum d(v_g) + \sum d(v_u)

Daraus folgt, dass sich die Summe der ungeraden Knotengrade aus einer geraden Anzahl von Summanden zusammensetzt, da nur dann die Summe der ungeraden Knotengrade gerade ist.

Anmerkung[Bearbeiten]

Dieser Schluss ist nur dann richtig, wenn man zeigen kann, dass die \sum d(v_g) gerade ist. Ansonsten würde der 2. Summand ebenfalls ungerade sein müssen, damit man auf ein gerades Ergebnis kommt. (\overline{1}+\overline{1}=\overline{0})

Nun man kann sich aber überlegen, dass \sum d(v_g) gerade sein muss:

Wenn der Grad eines Knoten gerade ist, bedeutet das nichts anderes, als dass er 2 \cdot n Nachbarn hat. Daraus folgt, dass immer nur gerade Zahlen addiert werden, wodurch auch die Summe gerade sein muss:

\Rightarrow \sum d(v_g) = 2 \cdot p (gerades Ergebnis)

Links[Bearbeiten]

  • Diskussion Informatik-Forum WS07 Beispiel 202