Graphentheorie - Beweishilfe
-
Hallo liebes Forum. Ich habe hier ein Problem. Und zwar muss ich folgendes beweisen:
Jeder Graph mit n >= 2 Knoten enthält mindestens zwei Knoten vom gleichen Grad.
Für n = 2 gilt das. Weil
Fall 1 : keiner der beiden Knoten hat hat eine Kante. Grad 0 bei beiden Knoten
Fall 2: beide Knoten haben eine Kante. Grad 1 bei beiden KnotenFür n = 3 gilt es auch, da ja n = 2 enthalten ist.
Für n >= 2 muss es dann doch auch gelten da n = 2 in n >=2 immer enthalten ist.Geht das als Beweis durch? Wenn nicht.. wie soll ichs dann beweisen?
Bin für jeden Tip dankbar.
der exa
PS: habs ausversehen unter datenbanken geschickt.. tut mir leiden.. deswegen poste ich es nochmal hier
-
Der Grad jedes Knotens ist ja <= n, >= 0. Es kann aber nicht gleichzeitig einen von Grad 0 und n geben. Jetzt Schubfachprinzip.
-
könntest du das mit dem Schubfachprinzip bitte etwas ausbreiten?
kann es sein das du dich etwas vertan hast, weil maximale grad eines knotens is docht 0 <= Grad <= n - 1 ..für K3 ist maximale grad ja 2 ... oder liege ich falsch und min grad ist 1?
-
ok, ein Knoten kann nicht mit sich selbst verbunden sein, also in [0,n-1]. Das sind n Möglichkeiten, von denen n-1 ausgeschöpft werden können (da nicht 0 und n-1 gleichzeitig). Es gibt n Knoten, also n Knotengrade, welche je einer von n-1 Werten sein kann. Also gibt es zwei Knoten mit demselben Grad
-
... les mir das jetzt noch 3 mal durch dann hab ichs inne
vielen vielen dank für die superschnelle antwort.. echtes speed forum bei euch...
-
Exavier schrieb:
... les mir das jetzt noch 3 mal durch dann hab ichs inne
vielen vielen dank für die superschnelle antwort.. echtes speed forum bei euch...
