Induktion und Graph Theory und Euler's Formula?
Guten Morgen :)
Ich habe ein Problem mit folgender Frage:
Mir ist nicht klar, wie ich hier mit der Induktion beweisen kann. Also meistens ist es ja so, dass man die linke und die rechte Seite vom Gleichzeichen mit einander abgleicht vor und nach dem Induktionsschritt... Aber hier verstehe ich nicht wie man den Induktionsschritt machen soll.
Folgendes habe ich schon:
Kann mir da jemand weiterhelfen?
Ich wäre sehr dankbar dafür :)
2 Antworten
Du musst von V auf V+1 schliessen, d.h was passiert, wenn du einen neuen Punkt dazu nimmst, mit V (-> V`=V+1), E (E' -> ?) und F (F'-> ?). Zeige, dass V'-E'+F' = V-E+F.
Greife zur strukturellen Induktion.
Beginne mit 2 verbundenen benachbarten Vertices und nehme nun einen weiteren hinzu, sodaß ein Dreieck gebildet wird, das keinen anderen Vertex einschließt.
Wiederhole den Prozess induktiv, bis alle Vertices konsumiert sind. Beobachte, wie sich mit Hinzunahme eines Vertex E und F verändern.
(Du kannst auch alternativ überlegen, was passiert, wenn in einem Dreieck ein Vertex hinzukommt und für den Einschluß mehrere Vertices ließe sich der Prozess rekursiv wiederholen).