(Twitter)
0
Einen richtigen Ansatz habe ich nicht. Aber für d=3 habe ich einen Graphen zeichnen können.
Zeichne erst ein Fünfeck. Dann gilt d=2, |V|=2²+1=5. Da gilt es schonmal. Kleiner geht nicht.
Ich versuche mal zu beschreiben, wie Du für d=3 an den Graphen kommst, den ich gefunden habe.
Wenn jetzt d=3 sein soll, dann muss jede Ecke eine zusätzliche Kante bekommen. Mit den vorhandenen Ecken darf diese nicht verbunden werden (Kreis wäre zu klein). Die vorhandenen Ecken haben ja maximal einen Abstand zueinander von 2. Wenn mal also zwei nicht benachbarte Ecken nimmt, dann müssen mindestens zwei weitere Ecken dazukommen, damit der Kreis mindestens eine Länge von 5 hat.
Damit haben die beiden neuen Ecken aber auch nur Grad 2 und brauchen noch eine dritte Kante...
Die beiden neuen Ecken haben zu den beiden noch nicht verwendeten Ecken des ursprünglichen Fünfecks jeweils den Abstand 3, also brauchst Du hier noch jeweils eine Zwischenecke. Damit sind es bisher 9 Ecken.
Die zehnte neue Ecke wird mit den beiden Zwischenecken von gerade verbunden und mit der Ecke vom ursprünglichen Fünfeck, die im ersten Kreis liegt und noch keine dritte Kante hat.
Wenn ich nichts übersehen habe, hat dann dieser Graph 3²+1=10 Ecken und kein Kreis ist kleiner als 5.
Ich habe in mein altes Graphentheorie-Skript aus Uni-Zeiten geguckt, da wurde diese Behauptung nicht bewiesen.
Mein Gefühl sagt mir einerseits, dass Du mit diesem maximalen Abstand von 2 arbeiten musst um die Anzahl neuer Ecken zu begründen, und es riecht nach vollständiger Induktion. Außerdem müsste es in der Vorlesung oder Übung vorher vielleicht bewiesene Sätze geben, die weiterhelfen.
Andererseits habe ich in meinem Skript einen Beweis entdeckt, der auf Wahrscheinlichkeiten basierte - es kann also auch eine ganz andere Beweisidee zum Ziel führen.
Nachbemerkung:
Ich weiß nicht, ob mein beschriebenes Vorgehen auf größere Grade so einfach erweiterbar ist. Der Satz von Cayley (Bestimmung der Anzahl der benannten Bäume mit n Ecken) heißt so, weil der Namensgeber die Behauptung aufstellte, zwei Schritte vorrechnete und dann schrieb "Rest durch Induktion" - das war aber lange nicht so einfach wie er sich das dachte. Die gültigen Beweise kamen erst später bzw. von anderen in anderen Zusammenhängen.
Insofern ist Vorsicht geboten.
Zeichne erst ein Fünfeck. Dann gilt d=2, |V|=2²+1=5. Da gilt es schonmal. Kleiner geht nicht.
Ich versuche mal zu beschreiben, wie Du für d=3 an den Graphen kommst, den ich gefunden habe.
Wenn jetzt d=3 sein soll, dann muss jede Ecke eine zusätzliche Kante bekommen. Mit den vorhandenen Ecken darf diese nicht verbunden werden (Kreis wäre zu klein). Die vorhandenen Ecken haben ja maximal einen Abstand zueinander von 2. Wenn mal also zwei nicht benachbarte Ecken nimmt, dann müssen mindestens zwei weitere Ecken dazukommen, damit der Kreis mindestens eine Länge von 5 hat.
Damit haben die beiden neuen Ecken aber auch nur Grad 2 und brauchen noch eine dritte Kante...
Die beiden neuen Ecken haben zu den beiden noch nicht verwendeten Ecken des ursprünglichen Fünfecks jeweils den Abstand 3, also brauchst Du hier noch jeweils eine Zwischenecke. Damit sind es bisher 9 Ecken.
Die zehnte neue Ecke wird mit den beiden Zwischenecken von gerade verbunden und mit der Ecke vom ursprünglichen Fünfeck, die im ersten Kreis liegt und noch keine dritte Kante hat.
Wenn ich nichts übersehen habe, hat dann dieser Graph 3²+1=10 Ecken und kein Kreis ist kleiner als 5.
Ich habe in mein altes Graphentheorie-Skript aus Uni-Zeiten geguckt, da wurde diese Behauptung nicht bewiesen.
Mein Gefühl sagt mir einerseits, dass Du mit diesem maximalen Abstand von 2 arbeiten musst um die Anzahl neuer Ecken zu begründen, und es riecht nach vollständiger Induktion. Außerdem müsste es in der Vorlesung oder Übung vorher vielleicht bewiesene Sätze geben, die weiterhelfen.
Andererseits habe ich in meinem Skript einen Beweis entdeckt, der auf Wahrscheinlichkeiten basierte - es kann also auch eine ganz andere Beweisidee zum Ziel führen.
Nachbemerkung:
Ich weiß nicht, ob mein beschriebenes Vorgehen auf größere Grade so einfach erweiterbar ist. Der Satz von Cayley (Bestimmung der Anzahl der benannten Bäume mit n Ecken) heißt so, weil der Namensgeber die Behauptung aufstellte, zwei Schritte vorrechnete und dann schrieb "Rest durch Induktion" - das war aber lange nicht so einfach wie er sich das dachte. Die gültigen Beweise kamen erst später bzw. von anderen in anderen Zusammenhängen.
Insofern ist Vorsicht geboten.
Diese Antwort melden
Link
geantwortet
joergwausw
Punkte: 2.37K
Punkte: 2.37K
Erst einmal danke für die ausführliche Antwort. Tatsächlich bin ich fast genauso vorgegangen. Nur bin ich nach einer Weile zu dem Schluss gekommen, wenn ich meinen minimalen Grad erhöhen will, brauche ich zuviele neue Ecke, was wiederum zu einem unendlichen Graphen geführt hatte, wodurch ich auch nur auf einen möglichen kam, für den der Satz gilt. Allerdings weis ich nicht, ob das als Beweis ausreicht.
─
gunnar0815
24.10.2021 um 22:29
Naja, ich hatte ja schon mal zwei gefunden... der Trick besteht ja darin, dass man eben nicht unbegrenzt neue Ecken erzeugt, sondern die "noch offenen" Ecken in cleverer Weise nutzt. Denn nur so kann die untere Grenze gezeigt werden.
─
joergwausw
24.10.2021 um 23:44
