Forum / Bits und Bytes / Induktiver Beweis bei einem Graphen

Komischer Titel, aber mir fällt nix besseres ein.

Wir haben ein Übungsblatt, das mich mit der letzten übrigen Aufgabe noch zur Verzweiflung bringt. Alle anderen habe ich.

Vielleicht könnt ihr mir ja helfen. (Ich denke, man muss es per vollst. Induktion beweisen)

Aufgabe:
Für den ungerichteten Graphen G = (V,E) gilt: Für alle x aus V gilt: d(x) >= a und der kürzeste Kreis (der Länge != 0) hat Länge 5. d(x) gibt den Grad an.

Beweisen Sie, dass G mindestens a² + 1 Knoten besitzt.

Meiner Meinung nach ist der Induktionsanfang bei a = 2. Da kann man ja einfach ein Bild malen und sieht, dass es 5 Knoten gibt, die alle mind. Grad 2 haben (einfach alle miteinander verbinden).

Jetzt habe ich ein bisschen rum gerechnet und bin darauf gekommen, dass beim Schritt a -> a+1 soviele neue Knoten dazu kommen müssen (mindestens): (2 ( a-1) +1).

Leider habe ich jetzt keine weiteren Ansätze für die Aufgabe mehr. Habt ihr eine Idee?

(Vorlesung ist übrigens "Grundbegriffe der Informatik")

[zustimmen]

Hsohnlol

Experte (offline)

Dabei seit 09.2010
1822 Beiträge

Geschrieben am: 08.12.2011 um 20:05 Uhr

aber das weiss doch jedes kind :kopfschuettel:

[zustimmen]

studentchen

- 34
Fortgeschrittener (offline)

Dabei seit 06.2011
81 Beiträge

Geschrieben am: 08.12.2011 um 20:07 Uhr

Zitat von Hsohnlol:

aber das weiss doch jedes kind :kopfschuettel:

Ja, dann verzehl

[zustimmen]

[Antwort schreiben]

Forum / Bits und Bytes