Graphentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:47 Di 17.01.2006 | | Autor: | dump_0 |
Hallo.
Ich hänge derzeit an einem Beweis und habe leider absolut keine Ahnung wie ich es anstellen soll, aber hier mal der zu beweisende Satz:
Beweisen oder widerlegen Sie:
Jeder Graph mit n [mm] \ge [/mm] 2 Knoten enthält mind. zwei Knoten vom gleichen Grad.
Also das es wohl stimmt kann man sich vorstellen, angenommen es gibt 2 Knoten die durch eine Kante verbunden sind, dann haben beide den gleichen Grad, gleiches gilt wenn beide nicht verbunden sind.
Nur wie zeige ich das für n Knoten ? Muss man auch die Anzahl der Knoten in dem Graph beachten, also für n gerade und ungerade ?
Würde mich sehr über Hilfe freuen.
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:19 Di 17.01.2006 | | Autor: | piet.t |
Hallo,
das ganze ist eigentlich eine ganz simple Abzählaufgabe. Überleg mal entlang der folgenden Fragen:
Wenn wir einen Graphen mit n Knoten haben, wie viele mögliche Werte gibt es dann für den Grad eines Knoten?
Und warum können der höchste und der niedrigste mögliche Grad nicht gleichzeitig auftreten?
Daraus folgt....?
Gruß
piet
|
|
|
|
