1 - Faktoren von Graphen

Math. Ann.201,269------282(1973) Q by Springer-Verlag1973

1-Faktoren von Graphen W. Mader

§ 0. Einf'fihrungund Bezeichnungen Unter einem Graphen verstehen wir hier einen endlichen, ungerichteten Graphen ohne mehrfache Kanten und ohne Schlingen. Wenn mehrfache Kanten, aber keine Schlingen zugelassen sind, sprechen wir von einem Multigraphen. Sei E(G) die Eckenmenge, K(G) die Kantenmenge des Graphen G = (E(G), K(G)). Die Kante zwischen den Ecken x und y bezeichnen wir mit Ix, y] = [y, x]; weiterhin sei IGI = IE(G)I und x e G sei gleichbedeutend mit x ~ E(G). Einen Weg mit den verschiedenen Ecken x und y als Endpunkten nennen wir einen x, y-Weg. Zwei x, y-Wege heil3en disjunkt, wenn sie nur x und y gemeinsam haben. Die Maximalzahlen disjunkter x, y-Wege in G bezeichnen wir mit/~(x, y; G) und fiir IGI>I definieren wir ~(G)= min #(x,y;G); ffir IGI
Ein Graph G heiBt n-fach zusammenh~ingend, wenn i~(G)>n ist; er heil~t n-minimal, wenn p(G)>n ist, aber l~(Gx,y)
d(G) = max (u(G - S) -ISl). S£E(6) Eine Verallgemeinerung I-3] des Satzes yon Tutte iiber die Existenz yon 1-Faktoren 1-11] besagt, dab der Defekt einer gr613ten Paarung in G gleich d(G) ist. Wir werden dieses Ergebnis hier aus dem bekannten Satz yon Hall (s. Satz 1.1 in § 1) herleiten. In [2] wurde gezeigt, dab ein 2fach zusammenh~ingender Graph mit einem 1-Faktor sogar mindestens 2 Faktoren 1-ten Grades enthiilt. 18 Math. Ann. 201

270

w. Mader:

Wir werden beweisen, dab dies auch schon f'fir briickenlose Graphen gilt. Bezeichnen wir mit F(G) die Anzahl der verschiedenen 1-Faktoren von G. In [12] wurde eine Funktion f ( n ) = min {F(G)Ip(G)>= n ^ F(G)> 0} definiert und fiir aUe natiirlichen Zahlen n wurde f(2n) > 2 n ( 2 n - 2) ( 2 n - 4)... 4- 2 und

f ( 2 n - 1) = ( 2 n - 1) ( 2 n - 3)... 3 . 1

bewiesen. Es wurde vermutet (Vermutung 3 aus [12]), dab/~(G) ~ 2n + 1 und F ( G ) = f ( 2 n + 1) nur fiir den Graphen G = K 2 , + 2 gilt, wobei K,~ der vollst~indige Graph mit m Ecken sei. Wir werden dies in § 3 beweisen. In [12] wurde das Problem gestellt, f(2n) fiir n > 3 zu bestimmen, und es wurde f ( 2 n ) > 2 n ( 2 n - 2)... 2 fiir alle n > 3 vermutet (Vermutung 2 aus 112]). Der Graph S, entstehe aus dem K2, durch Weglassen der Kanten eines 1-Faktors von K2,. I44r werden f ( 2 n ) = F(S,+O far alle n > 1 zeigen, und der Graph S,+ 1 wird sich Jar n > 2 als der einzige Graph G mit I~(G)> 2n und F(G)= f(2n) erweisen. Die Herleitung dieses Ergebnisses stiitzt sich ganz wesentlich auf eine Charakterisierung derjenigen n-fach zusammenhdn#enden Graphen G, Jar welche G - x J~r jedes x e G (n - 1)-minimal ist. Fiir x e G sei N(x, G) = {Yl Ix, y] e K(G)} und y(x, G) = IN(x, G)I. Fiir E' ~_E(G) defmieren wir N(E', G) = U N(x, G) - E' und fiir einen TeilXeE'

graphen H __cG sei N(H, G) = N(E(H), G). Isomorphe Graphen betrachten wir als gleich. Seien H und G zwei beliebige Graphen und H' und G' disjunkte Exemplare von H bzw. G. Sei H ~vG = H ' u G' and der Graph H + G entstehe aus H'wG' durch Hinzufiigen aller Kanten [h, g] mit k

h e H' und g • G'. Weiterhin sei kG = ~. G, mit G, = G f(ir alle x. Einen Weg schreiben wir als Folge von Ecken und Kanten. Fiir Ecken x und y auf dem Weg W sei W[x, y] der Teilweg von W, welcher x und y verbindet. Lm bedeute einen Kreis der L~inge m > 3. Analoge Bezeichnungen verwenden wir fiir Multigraphen.

§ 1. Benfitigte Resultate In diesem Paragraphen stellen wir einige S~itze und Lemmata zusammen, die wir bei der Herleitung unserer Ergebnisse benutzen werden. Einen paaren Graphen G, dessen Eckenmenge in die beiden unabh~tngigen Eckenmengen $ und T zerlegt ist, bezeichnen wir mit G [S, T]. Satz 1.1 (Hall-Ore). Sei G = G[S, T-J ein paarer Graph und mit festem 5 gelte IN(S', G)I > IS'l - ~ far alle S' ~_S. Dann existiert eine Paarung in G, die alle Ecken yon S mit Ausnahme oon hfchstens 5 Ecken enthdlt. Siehe Satz 7.3.3 in [10] oder Satz 3.2.1 in [9].

1-Faktoren von Graphert

271

Aus Satz 1.1 ergibt sich leicht Satz 1.2(KOnig). Sei G = G[S, T] ein paarer Graph. Fiir jedes R c=E(G), das yon jeder Kante yon G mindestens einen Endpunkt enthiilt, gelte fRI > ISl- 6. Dann existiert eine Paarung in G, die aUe Ecken von S mit Ausnahme yon h6chstens fi Ecken enthd'lt. Siehe Satz 14 von Kap. 14 in [7]. S a t z l . 3 . Sei M = M [ S , T ] ein paarer Multigraph mit F ( M ) > 0 . Dann existiert ein s ~ S, so dafl jede mit s inzidente Kante in einem 1-Faktor yon M liegt. Vergleiche S. 116 in [10]. Aus Satz 1.3 ergeben sich unmittelbar die beiden folgenden Lemmata. Lemma 1.1. Sei M = M[S, T] ein paarer Multigraph mit F ( M ) > 0 undJ~r alle s ~ S gelte y(s, M) > n. Dann ist F(M) > n. I_emma 1.2. Sei G = G[S, T] ein paarer Graph mit F(G) > 0 und f~r alle s ~ S gelte 7(s, G) ~ n. Dann ist F(G) > n !. In [12] wurde das folgende Ergebnis bewiesen. Satz 1.4. Fftr den Graphen G gelte #(G)> 2 und F(G)> O. Dann existieren zwei Ecken x und y in G, so daft jede mit x oder y inzidente Kante in einem 1-Faktor yon G liegt. 1 Siehe Korollar 1 in [12]. Aus Satz 1.4 ergibt sich insbesondere, dab jeder Graph G mit/~(G) > 2 und F(G) = 2 zwei Ecken vom Grad 2 enth~ilt. Noch einige Eigenschaften n-minimaler Graphen. Lemma 1.3. Ein Graph G mit #(G) > n ist genau dann n-minimal, wenn f'~r jede Kante Ix, y] ~ K(G) gilt p(x, y; G) = n. Siehe Lemma 1 in [4]. Lenuna 1.4. In jedem Graphen G mit #(G) > 3 und [GI > 5 gibt es zu je vier verschiedenen Ecken immer einen Kreis, der genau zwei dieser Ecken enthiilt. Siehe (5.6) in [5]. Satz 1.5. In jedem n-minimalen Graphen G spannen die Ecken yore Grad > n einen Wald auf. Siehe Korollar 1 in [8].

Satz 1.6. Der Graph G sei n-minimal und es sei ~ : = max {7(x, G)[Xe G}. Dann ist die Anzahl der Ecken vom Grad n in G grOfler oder gleich max {n + 1, ~}. Siehe Satz 4 und Korollar 2 in [8]. 1 s. s. 281. 18 •

272

W. M a d e r :

§ 2. l-Faktoren in beliebigen Graphen Zun~ichst wollen wir den Satz von Tutte-Berge tiber den Defekt einer gr513ten Paarung aus dem Satz 1.1 yon Hall-Ore herleiten. Ich werde mich dabei kurz fassen, da inzwischen ein auf der gleichen Idee beruhender Beweis des Satzes von Tutte fiber die Existenz yon 1-Faktoren erschienen ist [1]. Satz 2.1 (Tutte-Berge). Eine gr~]3te Paarun# im Graphen G hat den Defekt d(G) = max (u(G - S) - ISI).

Beweis. Wir induzieren fiber IGI. Sei So (beziiglich der Inklusion) maximal unter den S~_ E(G) mit u ( G - S ) - ISI = d(G). Seien C~ ..... C, die Komponenten yon G - So. Wegen der Maximalitat yon So sind diese Komponenten alle ungerade. Sei C eine der Komponenten von G - So, c e C und C' = C - c. Sei S c=E(C'). Da IC'I gerade ist, gilt u(C' - S) =- ISl (rood2). Witre u ( C ' - S ) > ISI, dann wiire also u ( C ' - S ) > JSI + 2 und es wiirde folgen u(G - (So u S u {c})) = u(G - So) - 1 + u(C' - S) > ISol + d(G) + ISl + 1 im Widerspruch zur Maximalit~it von So. Somit ergibt sich d(C') = 0 und also nach Induktionsannahme F(C') > O. Sei 1C {1..... n} und N~ = U N(C~, G) c_So. Es gilt offensichtlich iel

u(G-IV~) > I11 und nach Definition yon d(G) weiterhin u ( G - N t ) - IN~I l l l - d ( G ) . Nach Satz 1.1 existieren somit d(G) = ISol unabh~ingige Kanten ls, x J mit s e So und x~ e Ci,, wobei is4:i~, ffir s4:s' gilt. Sei y~eC~ f a r / e l : = {1..... n } - { i s l s e S o } . Nach dem vorhergehenden Abschnitt gilt F(C~, - x~) > 0 fiir alle s e S0 und F(Ci - Yi) > 0 ffir alle i e I. Zusammen mit den unabhiingigen Kanten Is, x j Fur s e So erhalten wir also einen 1-Faktor yon G - {Y~Ii e 1}, d. h. eine Paarung in G vom Defekt III =d(G). Da es offensichtlich keine Paarung von kleinerem Defekt geben kann, ist Satz 2.1 bewiesen. n-

Wir wollen noch das folgende Ergebnis aus dem Beweis von Satz 2.1 festhalten.

Lemma 2.1. Sei S ~_E(G) maximal mit u ( G - S ) - ISI = d(G). Fiir jede Komponente C t,on G - S und jedes c e C gilt dann F ( C - c ) > O . Es existiere_n ISl unabhiineige Kanten [s, x~] mit s e S, wobei k eine zwei der x, in der aleichen Komponente yon G - S liegen, und jedes solche System yon Kanten I~iJ3tsich zu einer grfflten Paaruna yon G fortsetzen. Kotzig stellte das Problem (Problem 6 auf S. 494 in [13]), die Graphen G mit F(G) = 0 zu bestimmen, fiir welche jeder Graph G' mit E(G') = E(G) und K(G')3K(G) einen l-Faktor besitzt. 2 Alle Graphen der Form 2 s. S. 281~

l-Faktoren von Graphen

273

n+2

K n + U K2~+1, wobei n und die k~ beliebige, nicht negative, ganze v=l

Zahlen sind, haben diese Eigenschaft, u n d e r vermutete, dab es auBer diesen Graphen und den vollst~indigen Graphen K2n+l auch keine weiteren Graphen mit dieser Eigenschaft gibt. Diese Vermutung l~tBt sich mit Hilfe yon Satz 2.1 leicht beweisen. Sei also ein Graph G =~K2~+ 1 (fiir alle n) mit F(G) = 0 gegeben, so dab jeder Graph G', der aus G durch Hinzufiigen einer neuen Kante entsteht, einen 1-Faktor enth~ilt. Es existieren x,y ~ Gmit I-x, y] ~ K(G). Der Graph G' = (E (G), K(G)u {Ix, y]}) enth~ilt einen 1-Faktor, also enth~ilt G eine gr613te Paarung vom Defekt 2. Nach Satz 2.1 gilt somit d(G) = 2 und es existiert ein S ~_E(G) mit u(G - S) =lSI +2. Seien C1 ..... C,+2 die ungeraden Komponenten von G - S , wobei n = ISt ist. Es gibt keine gerade Komponente C von G - S, da auch naeh Hinzufiigen einer Kante l-c, c'] mit c ~ C und c' ~ Cl kein 1-Faktor existierte. Da ebenso nach Hinzufiigen einer Kante Ix, y] mit x e Cv und y ~ C~ oder mit x s C~ und y s S oder mit x ~ S und y ~ Skein 1-Faktor existiert, sind alle diese Kanten in G vorhanden und G hat somit die angegebene Gestalt. Genauso lassen sich auch alle Graphen bestimmen, deren Defekt sich durch Hinzuff4gen einer beliebioen, neuen Kante verrinoert. Es sind dies niimlich die vollstiindi#en Graphen und alle Graphen n+2+k

der Form K n +

U

K 2k~+2, wobei n, k und kv beliebioe, nicht negative,

v=l

ganze Zahlen sind. Sei nun G ein (nicht leerer) Graph mit F(G)> 0 und sei S ~_E(G) maximal mit u ( G - S ) = ISt. Da F(G)>0, insbesondere IGI gerade ist, gilt u(G - x) = 1 fiir jedes x e G und somit ist S 4=I~. Wenn S nur aus einer Ecke, etwa s, besteht, liegt nach Lemma 2.I jede mit s inzidente Kante in einem 1-Faktor von G. Wenn es ein S c=E(G) (also auch ein maximales) mit u(G - S) = ISl und ISl >- 2 gibt, dannist Seine trennende Eckenmenge von G. Durch mehrfache Anwendung des folgenden Satzes lassen sich diejenigen Graphen charakterisieren, welche genau einen 1-Faktor enthalten. Satz 2.2. Wenn F(G)= 1 f~r den zusammenhdn#enden Graphen G gilt, dann existiert eine Kante Ix, y] e K(G), so daft G~,y aus zwei unoeraden Komponenten besteht.

Beweis. Sei S ~_E(G) maximal mit u ( G - S)= ISI. Dann ist S + fl und nach Lemma 2.1 und Satz 1.3 existiert eine (ungerade) Komponente yon G - S, die durch genau eine Kante k mit S verbunden ist. Diese Kante k hat die gewiinschte Eigenschaft.

274

W~Mader:

In [2] wurde gezeigt, dab f~Jr jeden 2fach zusammenh~ingenden Graphen G mit F(G)> 0 sogar F(G)> 2 gilt. Aus Satz 2.2 ersieht man, dab es geniigt, G dabei als 2fach kantenzusammenh~ingend vorauszusetzen. 3 (Ein Graph G mit IGt > 1 heiBt n-fach kantenzusammenhangend, wenn fiir alle K' c=K(G) mit Ig'l < n der Graph (E(G), K - K') zusammenh~ingend ist.) Satz 2.3. Der Graph G mit F (G) > 0 sei n-fach kantenzusammenhiingend. Dann #ilt F(G) >=n.

Beweis. Sel S ~ E(G) maximal mit u(G - S) = ISI. Dann ist S * 0 und jede Komponente von G - S ist wegen des n-fachen Kantenzusammenhangs durch mindestens n Kanten mit S verbunden. Mit Hilfe der Lemmata 2.1 und 1.1 ergibt sich somit die Behauptung. Bemerkun#. Satz 2.3 gilt ebenso fiir Multigraphen und ist hierftir bei beliebiger Eckenzahl bestm6glich, wie man sich leicht iiberlegt. Fiir Graphen G gilt aber sogar F(G) > n fiir n > 4. 4 Wir wollen noch ein Ergebnis herleiten, das eine ~ihnliche Form wie Satz 2.1 hat. Wir nennen einen Graphen einen linearen Graphen, wenn er aus eckendisjunkten Kreisen und Kanten besteht. (Er enthalte keine isolierten Ecken !) Ein gr6Bter linearer Teilgraph von G sei ein linearer Teilgraph yon G mit m6glichst vielen Ecken. Mit i(G) bezeichnen wir die Anzahl der isolierten Ecken yon G. Satz 2.4. Fi~ einen gri~J3tenlinearen Teilgraphen H yon G gilt IGI - IH[ =

max

(i(G - S ) - I S I )

Beweis. Es ist klar, dab fiir jeden linearen Teilgraphen H yon G gilt IGl - IHI > 6 = max (i(G - S) - ISl), s~E(a)

Um einzusehen, dab es cinch linearcn Teilgraphen H yon G mit [G[ - ]HI ~ ~ gibt, bilden wir mit Hilfc yon G cinch paaren Graphen G'. Wcnn E(G) = {x 1..... x~} ist, scicn Yl ..... y~ davon verschiedcne, weitere n Eckcn. G' wird nun definiert durch E(G')=E(G)u{yx ..... y~} und K(G') = {Ix v, y~] l [x~, x~] E K(G)}. Sei R~_E(G') mit {x,y}c~R*O fiir jede Kante [x,y]~K(G'). Sei I = { v l x ~ e R ^ y~eR} und T = { v l x v ~ R ^ y~¢R}. Sei [xv, x~]~K(G) mit v e I. Da xv ¢ R und y~ ~ R gilt, folgt y, E R und xu e R, also # E 1. Somit ist x, ftir a l l e v e 7 eine isotierte Ecke von G - { x ~ l / ~ e I}. Da I/I _- I G I - ~ und nach Satz 1.2 existiert eine Paarung P in G', die alle Ecken x~ ..... x~ bis auf h6chstens ~ enth~ilt. Sei H' der Teilgraph von G, der von denjenigen Kanten yon G induziert a s. S. 2 8 L a s. S. 2 g l .

1-Faktoren yon Graphen

275

(erzeugt) wird, welche den Kanten von P ,,entsprechen". Ffir jede Ecke x e H' gilt 1 < 7(x, H') < 2, also besteht H' aus Kreisen und Wegen. Sei k die Anzahl der Komponenten von H', welche Wege der L~inge ~ 2 sind. Dann gilt IH'I > IK(P)t + k. Der Graph H entstehe nun durch Weglassen yon Kanten und Ecken aus H' auf folgende Weise: a) Wenn W eine Komponente von H' ist, die aus einem Weg der ungeraden L~inge l besteht, lassen wir die 2-te, 4-te ..... ( l - 1)-te Kante von W aus H' fort. b) Wenn W eine Komponente von H' ist, die aus einem Weg der geraden L~inge l besteht, lassen wir eine der beiden Endecken von W fort und verfahren mit dem tibrigbleibenden Weg der L~inge t - 1 wie unter a). Dann ist H ein linearer Teilgraph von G und es gilt IHI > IH'I- k > IK(P)I > IGI- 6, womit Satz 2.4 bewiesen ist.

Bemerkuno. Umgekehrt ergibt sich Satz 1.2 unmittelbar aus Satz 2.4. Sei J(G)={xly(x, G)=0}. Der paare Graph G[S, T] erf~ille die Voraussetzungen von Satz 1.2 und sei R c=E(G). Dann liegt von jeder Kante von G mindestens ein Endpunkt in (Rc~S)w(T-J(G-R)). Nach Voraussetzung gilt also 1 R n S I + I T - J ( G - R ) I > I S I - ~ und analog folgt IRc~ TI + IS - J ( G - R)I > ISl - ~. Durch Addition ergibt sich i(G - R) - IRI < ITI - IS[ + 26. Nach Satz 2.4 existiert also ein linearer Teilgraph H von G mit IGI-IHI<-ITt-ISt+2& d.h. IH1=21SI-2~. Dieser Teilgraph H liefert uns die gesuchte Paarung. § 3. 1-Faktoren in n-fach zusammenhiingenden Graphen

Wir werden in diesem Paragraphen zeigen, dab der einzige Graph G mit iz(G)>m und F(G)=f(m) f/Jr ungerade m ~ 3 der Km+l (vgl. Vermutung 3 in [12]) und fiir gerade m = 2n > 4 der Graph Sn+ 1 := (n + 1) K"2 ist (vgl. Problem und Vermutung 2 in [12]), wobei Km den zum Km komplement~iren Graphen bezeichnet. Dabei werden diejenigen Graphen G eine Rolle spielen, f~ir welche fiir jedes x e G der Graph G - x (/~(G)- l)-minimal ist. Es sind dies genau alle Graphen der Form kKm+k'Lm+ 2 mit nicht negativen ganzen Zahlen m>= 1, k,k', wobei (k, k') #: (1, O) und =b(O,O) sei. l~berlegen wir uns zun~ichst Lemma 3.1. Sei G ein Graph mit i~(G)> n und F(G)>0. Dann gilt F(G) > n! oder jede Kante yon G #eh6rt zu einem 1-Faktor yon G.

Beweis. Sei x~E(G). Wegen F ( G ) > 0 gilt u ( G - x ) = 1. Also existiert ein S mit x ~ S ~_E(G), das maximal ist unter den S'~_ E(G) mit u(G-S')= IS'I. Wenn S = {x} ist, liegt nach Lemma 2.i jede mit x

276

W. Mader:

inzidente Kante in einem 1-Faktor von G. Wenn [Sl ~ 2 ist, gilt wegen it(G)> n sogar lSl > n und fiir jede Komponente C von G - S ist IN(C, G)[ > n. Nach den Lemmata 2.1 und 1.2 ergibt sich dann F(G)> n!. Lennna 3.2. Sei G ein Graph mit l~(G)~ n > 3 und mit F ( G ) = f ( n ) . Dann geh6rt jede Kante yon G zu einem 1-Faktor yon G und Gist n-minimal. Beweis. Man sieht leicht an Beispielen (es geniigt, die vollst~indigen Graphen zu betrachten), dab f(n) < n! fiir allen > 3 gilt. Somit liegt nach Lemma 3.1 jede Kante yon G in einem 1-Faktor yon G. Somit kann keine Kante Ix, y] ~ K(G) mit/z(G~.r) > n existieren, da sich sonst der Widerspruch F(G) = F(G~.y) + F(G - {x, y}) > f(n) + 1 ergibt. Also ist G n-minimal. Aus Lemma 3.1 ergibt sich unmittelbar das Ergebnis aus [12], dab F (G) > n(n - 2) (n - 4)... fiir jeden Graphen G mit g(G) _>_n und F (G) > 0 gilt. Denn nach Lemma 3.1 k6nnen wir annehmen, dab jede Kante von G in einem 1-Faktor liegt. Fiir beliebiges, aber festes x e G gilt (bei IGI > 2)

F(G)=

~

F(G-{x,y}).

(1)

yeN(x,G)

Da p(G - {x, y}) > n - 2 und F(G - {x, y}) > 0 fiir aUe y e N(x, G) gilt, folgt hieraus durch Induktion die Behauptung. Fiir ungerade n gilt somit f(n) = n(n - 2 ) ( n - 4 ) .... wie der Kn+ 1 zeigt. Aus (1) ergibt sich weiterhin F(G) >=nfln {n!, m f ( n - 2)}, wenn m den Maximalgrad yon G bezeichnet. Wenn F(G) = f ( n ) gilt und n > 3 ungerade ist, muB also G sogar regul~ir vom Grad n sein. Satz 3.t. Z u jedem n ~ 1 existiert genau ein Graph G mit it(G) > 2n + 1 und F(G) = f ( 2 n + 1), ntimlich der K2 ~+2. Beweis. Sei G ein Graph mit /~(G)>2n+ 1 und F ( G ) = f ( 2 n + 1). Dann geh6rt nach Lemma 3.2 jede Kante von G zu einem 1-Faktor und nach der vorhergehenden Bemerkung ist G reguliir vom Grad 2n + 1. Sei zun~ichst n > 2, und nehmen wir an, es existieren x, y ~ G mit Ix, y] ~ K(G). Dann ist ),(y, G - {x, x'}) > 2n fiir alle x' ~ N(x, G) und somit gilt wegen F(G - {x, x'}) > 0 und 2n - 1 > 3 sogar F(G - {x, x'}) > f ( 2 n - 1). Somit ergibt sieh der Widerspruch F(G) > (2n + 1)f(2n - 1) = f ( 2 n + 1) u n d e s folgt G = K2,+ 2. Fiir n = 1 fiihren wir nun die Annahme IGI > 5 zum Widerspruch. Sei x ~ G und N(x, G) = {Yl, Y2, Y3}. Nach Lemma 1.4 existiert ein Kreis C in G, der genau zwei der Ecken x, Yl, Y2, Y3 enth~t. Also gilt x ~ C; seien etwa y 2 e C und y 3 e C . Wegen F ( G ) = 3 gilt F ( G - { x , y ~ } ) = I. Somit existiert nach Satz 2.2 eine trennende Kante [z, z'] yon G' : = G - {x, Yl}. Wegen C~_ G' liegen Y2 und Y3 in der gleichen Komponente yon G'~,z,. Wenn etwa auch z zu dieser Komponente gehSrt, ist {z, Yl} eine trennende Eckenmenge von G im Widerspruch zu/,(G) >=3.

1-Faktoren yon Graphen

277

Als n~ichstes wollen wir zwei Klassen von Graphen charakterisieren, die fiir unsere Betrachtungen unangenehrne Eigenschaften besitzen. Wir sagen, der Graph G hat die Eigenschaft An, wenn g(G) ~ n ist und wenn j~r jede Kante Ix, y] ~ K(G) gilt: dedes System yon n disjunkten x, y-Wegen in G enthiilt alle Ecken yon G. Wit sagen, G hat die Eigenschaft A, wenn G fiir eine nicht negative, ganze Zahl n die Eigenschaft A n besitzt. Zun~ichst eine Umformung der Definition. (al) Ein Graph G mit #(G)_> n _> 1 hat genau dann die Eigenschaft An, wenn der Graph G - x f ~ alle x ~ G (n - 1)-minimal ist.

Beweis. Ein Graph G mit/~(G) > n => 1 hat genau dann die Eigenschaft A n, wenn fiir alle x e G und f ~ alle [y, y'] e K(G - x) gilt/~(y, y'; G - x) 1. Dies wiederum ist nach Lemma 1.3 genau dann der Fall, wenn der Graph G - x fiir alle x ~ G (n - 1)-minimal ist. =

n -

(a2) Jeder Graph G mit der Eigenschaft An ist reguliir vom Grad n.

Beweis. Sei x ~ G. Wenn ";(x, G ) = 0 ist, muB K ( G ) = 0, also n = 0 sein. Wenn ),(x, G ) > 0 ist, sei y ~ N(x, G). Dann existieren n disjunkte x, y-Wege W1..... Wn und fiir diese gilt E(G)= 0 E(Wv)" Der Weg Wv V=I

,beginne" etwa mit der Kante [x, x J . Dann ist x zu keinem z e Wv {xv, y} benachbart, da sonst der Weg W~ : x, [x, z], W~[z, y] zusammen mit den W~ fiir # 4: v e i n System yon n disjunkten x, y-Wegen bildete, auf denen die Ecke x, nicht liegt. Also gilt ~(x, G) = n. -

Satz 3.2. Ein Graph G hat genau dann die Eigenschaft A, wenn er sich in der Form kgm + k'Lm+ 2

mit nicht negativen, ganzen Zahlen k, k', m darstellen l?i]3t. Beweis. Betrachten wir einen Graphen der Form /~k.+ v=l

Li,

mit

k~>l, I,>3,

~t=l

welcher die Eigenschaft A besitzt. Da er nach (a2) regul~ir ist, folgt kl = k2 . . . . . k, = ll - 2 = 12 - 2 . . . . . l m - 2. Andererseits sieht man leicht, dab die Graphen kK.m+k'Lm+2 tats~chlich die Eigenschaft A besitzen. Wir zeigen nun durch Induktion fiber n, dab sich jeder Graph mit der Eigenschaft A~ in der angegebenen Form darstellen l~iBt. F i i r n = 0, 1, 2 ist dies ohne weiteres ersichtlich. Sei nun G ein Graph der Eigenschaft A, mit n>-3. Sei x e G und L ein Kreis yon G - x. Darm ist x in G zu einer Ecke von L benachbart. Denn nach (a0 ist der Graph G - x ( n - 1)-minimal,

278

W. Mader:

und nach Satz 1.5 existiert somit ein y e L mit y(y, G - x) = n - 1. Wegen V(y, G) > n folgt Ix, 3:] e K(G). Wir unterscheiden nun zwei F§lle.

1. Zu mindestens einer Kante [x, y] ~ K(G) existiert ein System yon n disjunkten x, y-Wegen W 1..... W~, so daft mindestens einer der Wege Wv die Ltinge > 4 hat. Sei [x, y] eine solche Kante und sei W~..... W~ ein solches System von x,y-Wegen, wobei etwa 114:,1>5 und 114"21=2 gilt. Der Weg Wv v v (von x nach y durchlaufen) enthalte etwa die Ecken x _- z vo, zl, z2v ..... zm~, z ~ + l = y . Wegen Eigenschaft A n gilt nur darm [z~,z~,]eK(G) f/Jr {z~, z~,.} 4={x, y}, wenn 1# -/a'l = 1 ist. Nehmen wir an, es sei [z~, z] ~ K(G) mit z ~ W~- {x, y} und v > 3. Betrachten wir den Kreis L, der aus [x, zl], I'z], z] und W~[z, x] besteht. Wie wir sahen, muB z~tl zu einer Ecke yon L, also wegen m 1 > 3 zu einer Ecke z' von W~[z, z]] benachbart sein. Wenn z'4: z wiire, k6nnten wir statt W1 und W~ die Wege und

w~ :x, Ex, zl], ~I, E~l, z], W,E~, y] w , : w ~ E x , z,],Ez,, Zml],Z,~, ~ ~ [Zm~,Y], Y

betrachten, um einen Widerspruch zur Eigenschaft A, zu erhalten, da z~ auf keinem der Wege W~, 14/' und Wu fiir # 4= v, 1 liegt. Also gilt z'= z und z] ist fiir jedes v > 3 h6chstens zu einer Ecke von W~ - {x, y} benachbart. Wegen y(z~, G)=n und aus Symmetriegriinden sind also z~ 1 und z,~ f ~ jedes v= 3 ..... n je zu genau einer Ecke yon W~-{x, y} benachbart, und zwar zu derselben. Diese Ecke bezeichnen wir mit z,. Betraehten wir nun die Kante [x,z]]. Die Wege W~:W,[x,z~], [z~,zl],z] fiir v > 3 bitden zusammen mit den Wegen W~:x, [x,y], W~ [y, z]] und W~ : x, [x, zl], z] ein System yon n disjunkten x, z]-Wegen. Nach Eigenschaft A, enthalten diese Wege alle Ecken yon G. Somit gilt W~[x, z,] = W ~ - y , also z~ =z~,~ fiir a l l e v __>3. Durch Betrachtung der Kante [y, z~,] ergibt sich analog z~ = z~ fiir allev > 3. Also gilt m~ = 1 und somit IW, l = 3 far v ~ 3.

Da G reguliir vom Grad n ist, folgt auch [z~, z~] ~ K(G) far allev > 3 und aUe/t mit 1 < # < m I. Somit gilt G = C + (G - E(C)), wenn C den Kreis bezeichnet, der aus Wx und der Kante [x, y] besteht. Fiir c : = ICI g;tlt c<-<_7(z~,G)=n. Man sieht leicht, dab G - E ( C ) die Eigenschaft A,_, besitzt. Nach Induktionsannahme und der den Beweis einleitenden Bemerkung ergibt sich somit, dab sich G in der angegebenen F o r m darstellen liiBt.

2. Fiir jede Kante Ix, 3,] e K(G) besteht jedes System yon n disjunkten x, y-Wegen nur aus Wegen der L2inge < 3.

1-Faktoren yon Graphen

279

Sei [x, y] e K(G). Dann existieren n disjunkte x, y-Wege W1..... IV.. Wegen A. gilt E(G)= 0 E(W.). Da

tw, I ___4 ftir allev gilt, ist jede Ecke

V=I

yon G zu x oder y benachbart. Hieraus folgt leicht, dab sich G mit geeigneten k, und m in der Form ~ g~k. schreiben l~iBt.Aus der Regularit~it /~=1

yon G ergibt sich dann wiederum k~ = k 2 . . . . . kin. Wir untersuchen nun noch eine nahe verwandte Klasse yon Graphen. Wir sagen, der Graph G hat die Eigenschaft B., wenn er n-minimal ist und wenn zu jedem x e G ein y ~ N(x, G) existiert, so daft f ~ jede Kante [z, z'] yon G - {x, y} gilt #(z, z'; G - {x, y}) < n - 2. Fiir n > 2 hat G nach Lemma 1.3 genau dann die Eigenschaft B., wenn G n-minimal ist und wenn zu jedem x e G eine Kante [x, y] s K(G) existiert, so dab G - {x, y} ( n - 2)-minimal ist. Eine solche Kante [x, y] nennen wir eine B-Kante. Wenn G die Eigenschaft B, fiir ein n > 1 besitzt, sagen wir, G hat die Eigenschaft B. Lemma 3.3. Der Graph G hat genau dann die Eigenschaft B, wenn er sich in der Form K l + kK,, + k'L,,+ 2 darstellen liiflt, wobei k, k', m nicht negative, ganze Zahlen mit (k + k') "m > 0 sind. Beweis. Die Graphen K 1 +kgm+k'Lm+2 mit ( k + k ' ) m > O haben die Eigenschaft B, da die Graphen kgm+k'Lm+2 die Eigensehaft A besitzen. Wir miissen nut noch zeigen, daB dies alle Graphen mit B sind. Der Graph G habe also die Eigenschaft B, mit n > 1. Wenn n = 1 gilt, ist G ein Baum mit IG[ > 2 und durch Betrachten einer Endecke yon G erkennt man sofort G = K I + K , , mit m = l G I - 1 . Sei nun n ~ 2 und G#:K,+I. Sei Ix, y] eine B-Kante von G. Da tier Graph G - {x, y} dann (n - 2)minimal ist, existieren nach Satz 1.6 mindestens n - 1 Ecken vom Grad n - 2 in G - {x, y}. Alle z ~ G - {x, y} mit 7(z, G - {x, y}) = n - 2 sind in G zu x und zu y benachbart. Da G n-minimal ist, existieren naeh Lemma 1.3 somit genau n - 1 Ecken vom Grad n - 2 in G - {x, y}. Also ist naeh Satz 1.6 tier Maximalgrad yon G - {x, y} kleiner oder gleich n - 1 und jedes z mit y(z, G - {x;y})= n - 1 ist in G zu genau einer der beiden Ecken x, y benachbart. Somit gilt ~,(z, G) = n fiir jedes z ~ E(G) - {x, y} und wegen ]G] > n + 2 ist y(x, G) > n oder ~(y, G) > n. Durch Betrachtung zweier B-Kanten von G erkennt man, dab genau eine Ecke Xo mit y(x 0, G) > n existiert und dab jede B-Kante yon G mit Xo inzidiert. Da jede Ecke yon G mit einer B-Kante inzidiert, ist G = xo + ( G - x0) und G - Xo hat nach (al) die Eigenschaft A,_ ~. Somit folgt Lemrna 3.3 aus Satz 3.2. Obwohl wires ftir das Folgende nicht ben6tigen, wollen wir uns noch kurz iiberlegen, welche n-fach zusammenh~ingenden Graphen dutch

280

W. Mader:

Weglassen zweier beliebiger Ecken ( n - 2)-minimal werden. Sei G ein solcher Graph und sei x e G. Dann hat G - x nach (al) die Eigenschaft An- 1 und ist somit nach (a2) regul~ir vom Grad n - 1. Also gilt Ix, z] eK(G) far alle z e G - x und es ist somit G = K,+ t- Die Bedingung, dab far je zwei Ecken x und y des n-minimalen Graphen G gilt/~(G - {x, y}) = n - 2, scheint, obgleich st~irker als Kontraktionsminimalit~it 5, fiir gr6Bere n die Struktur von G nicht mehr so wesentlich einzuschriinken, dab nur wenige iibersichtliche Typen die Bedingung erfiillen. Wir kommen nun auf das Problem zuriick, f(n) for gerade n zu bestimmen. F a r Sn : = rlK2 mit n > 1 gilt/~(S~) = 2n - 2. Da S, aus dem K2n durch Streichen der Kanten eines 1-Faktors entsteht, ergibt sich mit Hilfe des Prinzips der Inklusion und Exklusion sofort

wobei wir F(Ko)= 1 setzen. Es l~iBt sich auch eine Rekursionsgleichung far F(S~) herleiten. F a r [x, y] e K(S,+ l) mit n > 2 ist S n + l - { x , y } = K2 + Sn-1. Wenn man die 1-Faktoren von K 2 + Sn_ 1 danach unterscheidet, ob sie die Kante des K2 enthalten oder nicht, erkennt man F(K2 + Sn- 1) = F(S,_ 1) + F(S~). Durch Summation/iber alle mit einem festen x inzidenten Kanten [x, y] e K(S,+ 1) ergibt sich somit (a) F(S~+ 1) = 2n(F(S,) + F(S,_ 1)) fur alle n > 2. Hieraus folgt leicht (b) 2"n! < F(S~+ 1) < 2 n ( 2 n - 2)! flit alle n > 3. Durch den folgenden Satz werden nun das Problem, Vermutung 2 und der letzte Teil yon Vermutung 3 aus [12] erledigt. Satz 3.3. Fib" alle n > t gilt f ( 2 n ) = F(S~+ 1) und flit n > 2 ist der S~+ 1 der einzige Graph G rait #(G) > 2n und F(G) = f(2n).

Beweis. F a r n = l und n = 2 ist f(2n)=F(S,+~)=2"n! aus [12] bekannt. Zun~ichst iiberlegen wit uns, dab es auBer dem $3 keinen 4fach zusammenh~ingenden Graphen G mit F(G)= 8 gibt. Sei also G ein Graph mit/t(G) =>4 und F(G)= 8. Nach Lemma 3.2 geh6rt jede Kante von G zu einem 1-Faktor. Dann mu8 aber G r e g u l ~ vom Grad 4 sein und far jede Kante Ix, y] e K(G) gelten F(G - {x, y}) = 2. Nach Satz 1.4 existieren somit zwei Ecken z und z' mit r(z, G - {x, y}) = ~(z', G - {x, y}) = 2, d.h. zwei gemeinsame Nachbarn yon x und y in G. Man iiberlegt sich ohne Schwierigkeit, dab ein 4lath zusammenh~ingender 6 Graph vom Regularit~itsgrad 4, in dem je zwei benachbarte Ecken mindestens zwei 5 s.s. 281. s.S. 281.

1-Faktoren von Graphen

281

gemeinsame Nachbam haben, der K 5 oder der $3 sein muB. Also folgt G=S3. Wir beweisen nun Satz 3.3 durch Induktion iiber n. Sei G ein 2n-fach zusammenh~ingender Graph mit F(G)= f(2n), sei n ~ 3 und sei Satz 3.3 schon fiir alle n' < n bewiesen. Nach Lemma 3.2 liegt jede Kante yon G in einem 1-Faktor und G ist 2n-minimal. G l~iBt sich nicht in der Form K l + k g , , , + k ' L m + 2 darstellen. Denn fiir einen solchen Graphen H : = K l + k g , , , + k ' L , , , + z mit k + k ' > 0 gilt I H L - # ( H ) = m und Inl ist ungerade, wenn m gerade ist; also k6nnen nicht IH[ und p(H) beide gerade sein. Somit hat G nach Lemma 3.3 nicht die Eigenschaft B. Also existiert ein x ~ G, so dab fOx alley e N(x, G) der Graph C~ : = G - {x, y} nicht (2n - 2)-minimal ist. Somit gibt es eine Kante [y', y"] e K(G y) mit

/~(Gyr,y,,)>=2n - 2.

Nach Lemma 3.1 gilt (I) F(GY)>(2n-2)! oder (II)jede Kante yon Gy 9eh6rt zu einem 1-Faktor yon Gy. Wenn Fall I eintritt, folgt nach (b) mit (a) (1) F(GY) >

F(S.+O=F(S.)+F(S._I).

Wenn Fall II eintritt, ergibt sich nach Induktionsannahme (2) F(G y) = F(GyY,y,,)+ F(G y - {y', y"}) =>f ( 2 n - 2) + f ( 2 n - 4) = F(S,) + F(S,_ 1). In beiden Fallen ergibt sich somit weiter F(G)=

Z

F(Gr) > Zn(F(S,) + F(S,-1))= F(S,+ O •

y~/q(x,G)

Also gilt F(S.+ 1)= f(2n) und Fall I kann ffir kein y ~ N(x, G) eintreten, sondem fiir a l l e y ~ N(x, G) ist F(C~y,y,,)= f ( 2 n - 2). Nach Induktionsannahme ergibt sich C~y,,y,,= S., also insbesondere IGI = 2n + 2. Wie man leicht sieht, existiert abet nur ein (2n)-minimaler Graph mit 2 n + 2 Ecken, n~imlich der S.+ 1. Somit folgt G = S.+ 1 und Satz 3.3 ist bewiesen. 1 Es existieren sogar m Ecken (m: = min{?(x, G)lxe G}) mit dieser Eigenschaft, wie in meiner in den Mathematisehen Nachrichten erscheinenden Arbeit ,,Ober die Anzahl der yon den 1-Faktoren eines Graphen tiberdeekten Ecken" gezeigt wird. z Diese Graphen wurden yon Tutte ,,hyperprime" genannt und beim Beweis seines Faktortheorems (Satz 2,1 ftir d(G)=0) in [1 I] praktisch schon charakterisiert. 3 Dies l~il3t sieh auch leieht aus dem eben zitierten Satz yon Beineke und Plummer dureh Induktion herleiten. 4 In der Arbeit ,,l~ber die Anzahl der 1-Faktoren in 2fach zusammenh'angenden Graphen", die voraussichtlieh in den Mathematischen Nachrichten erscheinen wird, konnte ieh zeigen, dab fiir jeden n-fach kantenzusammenhiingenden Graphen G mit F(G)> 0 sogar F(G)~ f(n) gilt, 5 Eine Definition dieses Begriffs findet sich in [6]. 6 Es geniigt: zusammenh~ingend.

282

W. Mader: l-Faktoren von Graphen

Literatm 1. Anderson, I.: Perfect matchings of a graph. J. Combinatorial Theory 10, 183--186 (1971). 2. Beineke, L., Plummer, M.: On the 1-factors of a non-separable graph..l. Combinatorial Theory 2, 285--289 (1967). 3. Berge, C.: Sur le couplage maximum d'un graphe. C.R. Acad. Sciences 247, 258 (1958). 4. Halin, R.: A theorem on n-connected graphs. J. Combinatorial Theory 7, t50--154 (1969). 5. Halin, R.: Zur Theorie der n-fach zusammenhlingenden Graphen. Abh. Math. Sem. Univ. Hamburg 33, 133--164 (1969). 6. Halin, R. : Untersuchungen tiber minimale n-fach zusammenh~tngende Graphen. Math. Ann. 182, t75--188 (I969). 7. KSnig, D.: Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft 1936. 8. Mader, W.: Ecken vom Grad n in minimalen n-fach zusammenhlingenden Graphen. Arch. Math. 23, 219--224 (1972). 9. Mirsky, L.: Transversal theory. New York, London: Academic Press 1971. 10. Ore, O.: Theory of graphs. Amer. Math. Soc., Providence 1962. 11. Tutte, W.T.: The factorization of linear graphs. J. London Math. Soc. 22, 107--111 (1947). 12. Zaks, J.: On the l-factors of n-connected graphs. In 1-13]. 13. Combinatorial structures and their applications. Hrsg. R. Guy, H. Hanani, N. Sauer, J. Schonheim. New York: Gordon and Breach 1970.

Dr. W. Mader II. Mathematisches Institut der FU D-1000 Berlin 33 KSnigin-Luise-Str. 24/26 Deutschland ( Eingegangen am 22. November 1971)