A proof of Petersen's theorem. (Q1451481)

Ein Graph heißt regulär vom Grade \(n\), wenn in jeder Ecke genau \(n\) Strecken zusammenstoßen; die Eckenzahl ist die Ordnung des Graph. Ein regulärer Graph heißt primitiv, wenn er nicht durch Ubereinanderlegen zweier regulärer Graphen derselben Ordnung und geringeren Grades entsteht. \textit{Petersen}s Theorem (Acta math. 15 (1891), 193-220; F. d. M. 23, 115 (JFM 23.0115.*)-117), dessen Beweis von \textit{Brahana} (Annals of Math. 19 (1917) 59-63; F. d. M. 46, 835 (JFM 46.0835.*)) und \textit{Errera} (Dissertation, Brüssel 1921; F. d. M. 48, 664 (JFM 48.0664.*)) vereinfacht worden ist, besagt bekanntlich: Ein primitiver Graph dritten Grades besitzt wenigstens drei Blätter, d. h. Bestandteile, die mit dem Rest des Streckenkomplexes durch eine einzige Strecke verbunden sind. Verf. beweist diesen Satz in vier Schritten: (1) Ein ``einfacher Graph'', d. h. ein zusammenhängender regulärer Graph dritten Grades, der keine Blätter besitzt, von einer Ordnung größer als Zwei kann immer durch einen Graph geringerer Ordnung ersetzt werden, indem man eine Strecke wegläßt und die vier an diese Strecke angrenzenden Strecken geeignet zusammenheftet. (2) Nennt man einen regulären Graph dritten Grades ``gefärbt'', wenn seine Strecken in rote und blaue so eingeteilt, sind, daß in jeder Ecke eine rote und zwei blaue Strecken enden, so gilt: Jede Strecke eines gefärbten einfachen Graph liegt auf einer geschlossenen Kurve, deren Strecken abwechselnd rot und blau sind; durch Vertauschen der Farben längs der Kurve kann man die Strecke umfärben. (3) Jeder einfache Graph kann gefärbt werden. (4) Jeder reguläre Graph dritten Grades mit weniger als drei Blättern kann gefärbt werden.