Graphentheorie?

Hallo,

gibt es zusammenhängende Graphen bei denen nur ein Knoten einen ungeraden Grad hat?

Wenn ja welche wären das/welche Literatur gibt es dazu? Ich finde im Internet leider nichts brauchbares.

Answer 1

[FataMorgana2010]

Nein.

Die Anzahl der Knoten mit ungeradem Grad ist immer gerade. Das ist ein elementarer Satz aus der Graphentheorie, gilt auch für nicht zusammenhängende Graphen. Lässt sich leicht herleiten. Schau dir die Gesamtsumme der Knotengrade an. Die ist immer gerade (Warum? Weil jede Kante zu dieser Gesamtsumme 2 beiträgt).

Dann teile diese Summe auf: Addiere über die Knoten mit geradem Grad und dann über die mit ungeradem Grad.

Sei also E die Menge aller Kanten, V die Menge aller Knoten.

Erstmal die Addition über alle Knoten:

$2\ \cdot\ \mid E\mid\ =\ \sum_{v\ aus\ V}^{ }d_G\left(v\right)\$ Jetzt aufgeteilt:

$2\ \cdot\ \left|E\right|\ =\ \sum_{v\ aus\ V,\ d_G\left(v\right)\ gerade}^{ }d_G\left(v\right)\ +\ \sum_{v\ aus\ V,\ d_G\left(v\right)\ ungerade}^{ }d_G\left(v\right)$ Links steht eine gerade Zahl. Die erste Summe rechts ist eine Summe über lauter gerade Zahlen, also auch gerade. Also muss auch die zweite Summe gerade sein. Da aber in der zweiten Summe jeder einzelne Summand ungerade ist, muss die Anzahl der Summanden gerade sein.

Also kann die Anzahl der Knoten mit ungeradem Grad nicht 1 sein.

Woher ich das weiß: Studium / Ausbildung – Dipl.-Math. :-)