ungerichteter Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:51 Do 13.07.2006 | | Autor: | pauker |
| Aufgabe | | Sei G = (V,E) ein ungerichteter Graph ohne Schlingen und Mehrfachkanten. zeigen Sie: Wenn |V| grösser gleich 2 gilt, dann gibt es zwei Knoten mit gleichem Grad |
wie zeige ich das denn? ich habe wirkliche keine Ahnung wie ich das machen muss :-(
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:17 Do 13.07.2006 | | Autor: | felixf |
Hallo!
> Sei G = (V,E) ein ungerichteter Graph ohne Schlingen und
Der Graph ist endlich, oder? D.h. $|V| < [mm] \infty$?
[/mm]
> Mehrfachkanten. zeigen Sie: Wenn |V| grösser gleich 2 gilt,
> dann gibt es zwei Knoten mit gleichem Grad
> wie zeige ich das denn? ich habe wirkliche keine Ahnung
> wie ich das machen muss :-(
Es geht ganz einfach (hat aber auch ein wenig gedauert bis ich da drauf gekommen bin): Da nach Voraussetzung jeder Grad $< n$ sein muss (wenn $|n| = |V|$ ist). Also muss jede Zahl $0, 1, [mm] \dots, [/mm] n-1$ als Knotengrad vorkommen, wenn nicht zwei Knotengrade gleich sind. Wenn jedoch alle diese Zahlen vorkommen, dann ist ein Knoten mit allen $n-1$ anderen Knoten verbunden, d.h. jeder Knotengrad ist mindestens 1: ein Widerspruch!
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:01 Do 13.07.2006 | | Autor: | pauker |
kann ich das so als antwort schreiben? habe ich so gezeigt, dass es zwei knoten mit gleichem Grad gibt? danke dir für deine mühe
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Sa 15.07.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
