Der Begriff Gruph wird im folgenden iminer im Sinne von nichtleerer, endlicher, schlichter, uiigerichteter Graph verwendet. Hinsichtlirh der Terminologie halteri wir uns a n das Buch von SACHS [3]. Einleitend seien einige Regriffe zusamniengestellt. Die Anzahl der Kiioten i m Graphen G wird init IG 1, die Kante mit den Eckpunkten a uiid b init ( ( I b ) oder ( b a ) bezeichnet. a E CY, soll bedeuten, dal3 a ein Kiioten von G ist. Ein W e g UI in G wird als Knoten-Kantenfolge in der Forin w -: C L { Z 1 n ~x ~. * . a,_lx',-Iu, mit n 2 1, x, = (a,cIlT,) (i = 1, . . ., n -1 ) und a, + aj fur j + j ( i , j = I , . . . , YL) geschrieben. Wir nenneii diese Folge auch einen Weg uon C I ~ ncxch a,, . Die aus w durch Umkehr der Reihenfolge der Glieder entsteheiide Folge sei w 1. Unter der Lknge 1 (70) eines Weges 10 verstehen wir die Zahl cler Kanten des Weges w. Der A b s t c d g (a, b ) zweier Knoten u, b E G in G ist die Ldnge eines kiirzesten Weges zwischen a und b in G. Der Weg ?A) = a( .r( a, xi . . . L C , _ ~ x,_~ a, heiBt ein huwdtonscher Weg von G genm d m n , weiin n = / G 1 ist. Jeder Folge w = w (a, uI), wobei II)
ein Weq von a( narh a,, der Larige 1 (w) 2 % in G und (a, a t ) eine Kante in G ist. 1st eindeutig einKreis i n G zugeordnet, namlich der &us den in 7 7 vorkommenden Knoten und Kanten bestehende. Der Einfachheit halber werden wir die Folge LL' selbst als Kreis hezeichnen. 1st n =-Z(W) + I = /GI 2 3, so heifit 6 ein hamiltonscher Kreis in G. Um Fallunterscheidungen zu vermeiden, soll, falls G genau zwei Knoten n l , u, + ai hat, die Folge w = a l ( a , a,) a2(a2 a , ) bzw. a2(a, ai) al(ai a,) und, falls G aus genau einem Knoten a besteht, die Folge w = a (a u ) -dabei ist naturlich ( u a ) nur ein formales Paar und keine Kante -, ein ausgearteler liamiltonscher Kreis in G heil3en.