Ecken mit ungeradem Grad < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:42 Di 15.05.2007 | | Autor: | Frido22 |
| Aufgabe | | Zeigen Sie, dass die Anzahl der Ecken mit ungeradem Grad in einem Graphen gerade sein muss. |
?
ch habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:15 Di 15.05.2007 | | Autor: | wauwau |
vollständige Induktion nach Anzahl der Knoten (=Ecken) n
n = 2 ist klar
soll für n= k gelten.
mit 2l-1 < k Ecken ungeraden Grades
Jetzt kommt ein Knoten [mm] K_{N} [/mm] hinzu
dieser wird nun mit einem anderen der k Knoten - bezeichnen wir in als [mm] K_{A} [/mm] verbunden
Fall 1: [mm] K_{A} [/mm] bisher ungeraden Grades
bekommt geraden Grad daher Anzahl der Knoten im bisherigen k-Eckigen Graphen 2l-2, [mm] K_{N} [/mm] ist auch ungeraden Grades (+1) daher insgesamt 2l-2+1=2l-1 Gesamtgraph hat ungerade Anzahl Ecken ungeraden Grades
Fall 2: [mm] K_{A} [/mm] bisher geraden Grades
bekommt durhc die Verbindung ungeraden Grad (+1), [mm] K_{N} [/mm] ebenfalls ungeraden Grades (+1)
daher gesuchte Gesamtanzahl: 2l-1+1+1=2l+1 wiederum ungerade
dies kann man für jede Verbindung von [mm] K_{N} [/mm] zu Knoten des alten k-knotigen Graphen durchführen
|
|
|
|
