Herrn Professor HERBERT GROTSCH zum 65. Geburtstag am 24. Mai 1967 gewidmet Von HANSJOACHIM WALTHER in Ilmenau (Eingegangen am 22. 12. 1966) 1. Einleituiig I n der vorliegenden Arbeit untersuchen wir ausschliel3lich planare Graphen, also solche, die sich auf einer Kugeloberflache zeichnen lassen, ohne daB sich Kanten uberschneiden. Ferner beschranken wir uns auf regulure Graphen vom Grad XI, (k = 3, 4, 5 ) , das sind Graphen, in denen jeder Knotenpunkt mit genau li Kanten inzidiert. Ferner behandeln wir nur schlichte Graphen, d. h. Graphen ohne Schlingen und Mehrfachkanten, und xusammenhungende Graphen, also solche, in denen zwei beliebige Knotenpunkte stets durch mindestens einen Weg (einen einfachen Kantenzug) verbunden sind. Die zusammenhangenden Bestandteile eines Graphen heiflen seine Komponenten. Einen einfach geschlossenen Kantenzug nennen wir Kreis. Ein Kreis, der jeden Knotenpunkt eines vorgegebenen Graphen enthalt, heiBt HAMILTONkreiS des Graphen. Ein Graph heifit m-fach knotenxusammenhangend, wenn fiir jedes r < m der nach Entfernen von r beliebigen Knotenpunkten und der mit ihnen inzidenten Kanten entstehende Graph keine zwei Komponenten besitzt, deren jede nlindestens einen Knotenpunkt enthalt. Ein Graph heiSt xylilisch m-fuch zusammenhungend, wenn fur jedes r < m der nach Entfernen von r beliebigen Kanten entstehende Graph keine zwei Komponenten besitzt, deren jede mindestens einen Kreis enthalt. I n dieser Arbeit untersuchen wir nur ungerichtete Graphen. Zur Verkurzung der Schreibarbeit wolleii wir einen planaren, ungerichteten, schlichten, zyklisch m-fach zusammenhangenden, regularen Graphen vom Grade 3 als m-Graphen bezeichnen. Wir vermerken zunachst , daB ein schlichter planarer Graph regular hochstens vom Grade 5 ist. Ferner gibt es keinen m-Graph mit nz > 5
(ausgenommen der Tetraedergraph, der keine zwei disjunkte Kreise besitzt). Diese beiden Tatsacheii sind einfache Folgeruiigen aus dem ETJLERwhen Polyedersatz : Knotenpunktanzahl plus Flachenanzahl ist gleich Kantenanzahl plus 2 . Im Abschnitt 2 dieser Arbeit untersuchen wir ausschlieolich regulare Graphen vom Grad 3, genannt kubische Graphen.