Taillenweite im Graphen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:07 Mo 30.10.2006 | | Autor: | se7en |
| Aufgabe | | Zu Zeigen: Graph G hat Taillenweite 5 und Minimalgrad k, dann hat G mindestens [mm] k^2 [/mm] + 1 Knoten |
Hi, kann mir bitte jemand helfen uns sagen, wie ich das zeigen kann, danke schonmal
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
sei [mm] v\in [/mm] V. Dann hat v mindestens k Nachbarn, jeder von denen hat mindestens k-1 weitere Nachbarn, die paarweise verschieden sind, da sonst
ein Kreis der Länge 4 entstünde, also haben wir mindestens
1+ k+ [mm] k\cdot [/mm] (k-1) [mm] =k^2+1 [/mm] Knoten.
Gruss,
Mathias
|
|
|
|
