Verständnis Beweis Graphentheorie

Neue Frage »

MatheiLike Auf diesen Beitrag antworten »
Verständnis Beweis Graphentheorie
Hallo Matheboard,

kennt sich jemand ein wenig mit Graphentheorie aus? Ich verstehe den folgenden Beweis nicht richtig.

Satz: Besitzt ein -regulärer Graph einen -Faktor , so hat einen -Faktor für alle .

Beweis: Es wird ungerade und gerade unterschieden. Den Fall " gerade" verstehe ich, deshalb lasse ich ihn hier weg.
Im Fall " ungerade" folgt die Behauptung dieses Satzes wohl sofort aus dem ersten Satz von Petersen.

Dieser lautet:
Ein Graph ist genau dann -faktorisierbar, wenn er -regulär ist .

Nachzulesen ist das alles auf den Seiten 131-132 im diesem Skript:
users.informatik.haw-hamburg.de/~klauck/GKA/LVolkmann.pdf

Ich versteh nicht, wieso die Aussage aus dem ersten Satz von Petersen folgt. Im Fall ungerade, weiß ich dann nach diesem Satz, dass der Graph nicht -faktorisierbar ist. OK , aber wie kann ich damit auf die Aussage schließen?
Kann mir jemand helfen?

Vielen Dank im Voraus auch für die Möglichkeit hier zu fragen. smile
MatheiLike Auf diesen Beitrag antworten »
RE: Verständnis Beweis Graphentheorie
Hm,

also mir leuchtet es nicht ein.

Wie könnte man es alternativ beweisen? Jemand dazu eine Idee?

Ist ungerade, so folgt die Existenz aller weiterer ungerader Faktoren aus einem Satz von Katerinis. Steht auch im oben angegebenen Skript Satz 7.11 .

Bleibt dann nur noch die Existenz der Faktoren geraden Grades zu zeigen.

Hm , es existiert nach Voraussetzung ein -Faktor und die Anzahl an Ecken im Graphen muss gerade sein, da die Anzahl Ecken ungeraden Grades in einem bel. Graphen immer gerade ist. Außerdem könnte sonst wohl auch kein -Faktor existieren. Dafür muss die Eckenzahl gerade sein, wenn ich mich nicht irre.

Hat jemand dazu eine Idee?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »