Scheinklausuren zur Graphentheorie I vom Lehrstuhl II für Mathematik, Prof. Dr. L. Volkmann

Kianhwa Djie

kianhwa.djie@post.rwth-aachen.de

25. Juli 2003

1 Scheinklausur am 7. 7. 1995

Aufgabe 1.1 Es sei T ein Baum. Verbindet man in T alle Ecken vom Abstand 2 durch eine Kante, so bezeichnen wir den neuen Graphen mit T^{2}. Man zeige:

a) Ist n(T) ≥ 3, so besitzt T^{2} keine Brücke.

b) Ist n(T) ≥ 4, so ist T^{2} kein Kaktusgraph.

Lösung zu Aufgabe 1.1 a) Wähle eine beliebige Kante k = ab ∈ K(T^{2}). Es können zwei Fälle auftreten:

1. Fall: k = ab ∈ K(T).

Weil T zusammenhängend und n(T) ≥ 3, hat einer der beiden Punkte a oder b einen weiteren Nachbarn c in T. Sei ohne Einschränkung ac ∈ K(T) mit einem c ≠ b. Da d(c,b) ≤ 2 in T (tatsächlich ist sogar d(c,b) = 2 wegen der Baumeigenschaft von T, was nicht weiter interessiert), ist auch bc ∈ K(T^{2}). Insbesondere haben wir einen Kreis C = abca in T^{2}, der die Kante k enthält. Somit ist k keine Brücke.

2. Fall: k = ab ∈ K(T^{2}) \ K(T).

In diesem Fall ist d(a,b) = 2, Also gibt es einen Weg in T der Länge 2, welcher a mit b verbindet, das heißt: Es gibt ein c ∈ E(T) mit ac,bc ∈ K(T). Demnach haben wir wieder einen Kreis C = abca in T^{2}, der die Kante k enthält, womit k keine Brücke sein kann.

Insgesamt zeigt sich: T^{2} hat keine Brücken.

b) Wir müssen lediglich zeigen, dass es zwei verschiedene Kreise in T^{2} gibt, die eine gemeinsame Kante besitzen. Es sind zwei Fälle zu unterscheiden:

1. Fall: Es gebe eine Ecke a ∈ E(T), die mindestens drei Nachfolger b,c,d in T hat. Es ist d(b,c) ≤ 2 und d(b,d) ≤ 2 in T, folgt bc,bd ∈ K(T^{2}). Man erhält also die beiden Kreise C_{1} := abca und C_{2} := abda in T^{2}, welche zwar verschieden sind, aber trotzdem ab als gemeinsame Kante haben.

2. Fall: Alle Ecken haben höchstens zwei Nachfolger in T.

Wegen n(T) ≥ 4 und des Zusammenhangs von T gibt es vier Ecken a,b,c,d ∈ E(T) mit ab,bc,cd ∈ K(T). Demnach ist d(a,c) ≤ 2 und d(b,d) ≤ 2 in T, also ac,bd ∈ K(T^{2}). Dies liefert uns wieder zwei verschiedene Kreise C_{1} := abca und C_{2} := bcdb in T^{2} mit gemeinsamer Kante bc ∈ K(T^{2}).

Also ist T^{2} kein Kaktusgraph.

Aufgabe 1.2 Sei G ein zusammenhängender Graph mit folgenden Eigenschaften: μ(G) ≤ 2, δ(G) = 2, und es gebe eine Ecke e_{0} minimalen Grades, die keinem Kreis von G angehört. Berechnen Sie:

a) κ(G − e_{0}).

b) τ_{p}(G) für alle p ≥ 3; Dabei ist τ_{p}(G) die Anzahl der Ecken vom Grade p in G.

c) μ(G).

d) Geben Sie ein schlichtes Modell minimaler Ordnung an.

Lösung zu Aufgabe 1.2 a) Es ist d(e_{0},G) = 2. Seien a,b die Nachfolger von e_{0}. Es ist κ(G − e_{0}) = κ(G) + 1 = 2. Denn wäre dennoch κ(G−e_{0}) = κ(G), so gäbe es einen kürzesten Weg W = a··· b von a nach b in G−e_{0}. Dann wäre aber W = e_{0}a··· be_{0} ein Kreis in G, was der Voraussetzung widerspricht.

b) Wir verwenden die Formel 2τ_{0}(G)+τ_{1}(G)+2(μ(G)−κ(G)) = ∑ _{i=3}^{Δ(G)}(i−2)τ_{i}(G). Wegen δ(G) = 2 ist τ_{0}(G) = τ_{1}(G) = 0. Da weiterhin G zusammenhängend, ist κ(G) = 1 und demzufolge 2(μ(G) − κ(G)) ≤ 2. Wir erhalten somit: ∑ _{i=3}^{Δ(G)}(i − 2)τ_{i}(G) ≤ 2. Also gibt es keine Ecken vom Grad ≥ 5. Demnach haben alle Ecken ungeraden Grades den Grad 3. Weil G zusammenhängend ist, aber e_{0} auf keinem Kreis liegt, kann G nicht Euler’sch sein. Also gibt es Ecken ungeraden Grades. Nach dem Handschlaglemma ist die Anzahl derer gerade, also erhalten wir τ_{3}(G) ≥ 2. Aus der Ungleichung ∑ _{i=3}^{Δ(G)}(i − 2)τ_{i}(G) ≤ 2 ersieht man, dass keine weiteren Ecken vom Grad ≥ 3 existieren können. Insgesamt ergibt sich folgendes Bild: τ_{2}(G) = n(G) − 2 ≥ 1,τ_{3}(G) = 2 und τ_{i}(G) = 0 für alle i ∈ ℕ_{0}\ {2,3}.

c) Mit Hilfe der Gleichung 2τ_{0}(G) + τ_{1}(G) + 2(μ(G) − κ(G)) = ∑ _{i=3}^{Δ(G)}(i − 2)τ_{i}(G) und der obigen Ergebnisse folgt unmittelbar μ(G) = 2.

d) Man zeichne die Ecke e_{0} mit ihren beiden Nachfolgern a,b ein und setze den Graphen an a und b mit zwei vollständigen K_{3}-Graphen fort.

Aufgabe 1.3 Sei G ein zusammenhängender Graph und a ∈ E(G) eine feste Ecke. Beweisen Sie:

a) Es gibt ein Gerüst T ⊂ G mit d(a,T) = κ(G − a).

b) Sei G_{0} ⊂ G ein Euler’scher Teilgraph mit der Eigenschaft, dass jede Kante k ∈ K(G_{0}) \ K(T) mit a inzidiert. Man zeige, dass a eine gute Ecke von G_{0} ist.

c) μ(G_{0}) ≤ d(a,G) − κ(G − a).

Lösung zu Aufgabe 1.3 a) G − a hat n := κ(G − a) Zusammenhangskomponenten K_{1},...,K_{n}. Da jedes K_{i} zusammenhängend ist, gibt es Gerüste T_{1},...,T_{n} von K_{1},...,K_{n}. Man fixiere in jedem T_{i} eine Ecke t_{i} ∈ E(T_{i}) mit at_{i} ∈ K(G). Durch Hinzufügen der Kanten at_{i} ∈ K(G) für jedes i = 1,...,n erhält man ein Gerüst T von G mit d(a,T) = n = κ(G − a).

b) Angenommen, a wäre keine gute Ecke in G_{0}. Dann gibt es einen Kreis C in G_{0} mit a ∉ E(C). Nach Voraussetzung ist dann K(C) ⊂ K(T). Also ist C ein Kreis in T, was der Baumeigenschaft des Gerüstes T widerspricht.

c) Es gilt: μ(G_{0}) = d(a,G_{0}) − κ(G_{0} − a) − s(a) ≤ d(a,G) − κ(G − a), wobei man die Ungleichungen d(a,G_{0}) ≤ d(a,G),κ(G_{0}− a) ≥ κ(G − a) und s(a) ≥ 0 verwende.

Aufgabe 1.4 Ein Digraph D heißt p-regulär, wenn d^{+} (x) = d^{−} (x) = p für jedes x ∈ E(D) gilt. Es sei T ein p-reguläres Turnier mit mindestens 5 Ecken. Zeigen Sie:

a) Jeder Bogen von T liegt in einem orientierten Kreis der Länge 3.

b) Jeder Bogen von T liegt in einem orientierten Kreis der Länge 4.

Lösung zu Aufgabe 1.4 Dies ist ein Spezialfall von Folgerung 5.4. Da dieser allerdings auf dem in der Vorlesung unbewiesenen Satz 5.4 aufbaut, verwenden wir hier eine elementare Alternativlösung:

a) Sei ab ∈ B(T) ein beliebiger Bogen. Wären alle p positiven Nachbarn von b, zu denen natürlich a und b nicht gehören, auch zugleich positive Nachbarn von a, so hätte a wegen ab ∈ B(T) mindestens p + 1 positive Nachbarn, was der Voraussetzung widerspricht. Also gibt es ein b^{+} ∈ N^{+} (b,T) mit b^{+} a ∈ B(T), was den orientierten Dreikreis abb^{+} a liefert, welcher den Bogen ab enthält.

b) Sei ab ∈ B(T) ein beliebiger Bogen. Es sind zwei Fälle zu unterscheiden:

1. Fall: Es gibt ein a^{−} ∈ N^{−} (a,T) \ N^{+} (b,T). a^{−} kann nicht die p Ecken in N^{+} (b,T) dominieren, da andernfalls a^{−} wegen a^{−} a ∈ B(T) mehr als p positive Nachfolger hätte. Also gibt es ein b^{+} ∈ N^{+} (b,T) mit b^{+} a^{−} ∈ B(T), was zum orientierten Kreis abb^{+} a^{−} a führt.

2. Fall: N^{−} (a,T) = N^{+} (b,T).

Man beachte, dass ein 1-reguläres Turnier nur mit 3 Ecken existiert. Es ist also p ≥ 2. Die Menge N^{−} (a,T) = N^{+} (b,T) hat dann p ≥ 2 Elemente. Seien c_{1},c_{2} ∈ N^{−} (a,T) = N^{+} (b,T) verschiedene Elemente mit c_{1}c_{2} ∈ B(T). Dann haben wir den Kreis abc_{1}c_{2}a.

In jedem Fall liegt der Bogen ab auf einem orientierten Kreis der Länge 4.

Aufgabe 1.5 Sei l ≥ 2 eine natürliche Zahl und G ein schlichter (2l +1)-regulärer Graph der Ordnung n(G) mit 2l +1 < n(G) ≤ 4l + 1. Zeigen Sie, dass G einen Euler’schen Faktor G′mit δ(G′) ≥ 3 besitzt.

Lösung zu Aufgabe 1.5 Alle n Ecken haben ungeraden Grad. Nach dem Handschlaglemma muss demnach n gerade sein. Da G schlicht, n(G) ≥ 4 und 2δ(G) = 2(2l + 1) ≥ n(G), folgt aus dem Satz von Dirac, dass G Hamilton’sch ist. Sei H ein Hamiltonkreis. Da n(G) gerade ist, kann man aus H jede zweite Kante entfernen und erhält somit einen 1-Faktor F. Indem man F aus G entfernt, erhält man einen 2l-Faktor G′. Dieser ist zusammenhängend. Denn angenommen, es gäbe zwei Komponenten K_{1} und K_{2} von G′. Als 2l-regulärer Graph müssen beide Komponenten mindestens 2l + 1 Ecken besitzen. Demnach wäre n(G) = n(G′) ≥ 4l + 2, was der Voraussetzung widerspricht. Also ist G′ein 2l-regulärer zusammenhängender Faktor von G, welcher Euler’sch ist, da alle Ecken geraden Grades sind.

Aufgabe 1.6 Es sei G ein bipartiter Graph mit der Bipartition A,B, und für alle x ∈ A gelte d(x,G) = Δ(G) ≥ 1. Zeigen Sie, dass in G ein Matching M mit |M| = |A| existiert.

Lösung zu Aufgabe 1.6 Sei S ⊂ A beliebig. Wir verwenden Folgerung 1.4 aus der Nachbarschaftsungleichung: δ(G)|S| ≤ Δ(G)|N(S,G)|. Also ist |S| ≤ |N(S,G)| für alle S ⊂ A. Nach dem Satz von König-Hall gibt es ein Matching M in G mit E(M) ∩ A = A. Insbesondere ist |M| = |A|.

2 Scheinklausur am 26. 10. 1995

Aufgabe 2.1 Sei G ein schlichter, zusammenhängender Graph und e_{0} ∈ E(G) eine fest gewählte Ecke. Für ab = k ∈ K(G) ist durch ρ(k) := |d(e_{0},a) − d(e_{0},b)| eine Kantenbewertung ρ : K(G) → ℝ erklärt. Dabei ist d(x,y) der Abstand von x und y in G.

a) Zeigen Sie: Für alle k ∈ K(G) gilt ρ(k) ∈ {0,1}.

b) Sei r ∈ ℕ_{0}. Der von der Menge {x ∈ E(G) | d(e_{0},x) = r} induzierte Teilgraph S_{r}(e_{0}) heißt e_{0}-Sphäre vom Radius r.

Beweisen Sie: Sind alle e_{0}-Sphären zusammenhängend, so gilt für ein ρ-Minimalgerüst T ⊆ G: ρ(T) = max_{x∈E(G)}d(e_{0},x).

Lösung zu Aufgabe 2.1 a) Sei k = ab ∈ K(G) beliebig und W = e_{0}··· a ein kürzester Weg von e_{0} nach a der Länge d(e_{0},a). Dann ist W′:= e_{0}··· ab eine Kantenfolge von e_{0} nach b der Länge d(e_{0},a) + 1. Insbesondere ist d(e_{0},b) ≤ d(e_{0},a)+1, also d(e_{0},b)−d(e_{0},a) ≤ 1. Analog zeige man d(e_{0},a)−d(e_{0},b) ≤ 1, woraus dann die Behauptung folgt.

b) ”≤“ Alle Sphären S_{r}(e_{0}) sind für r = 1,...,M:= max_{x∈E(G)}d(e_{0},x) nichtleer und zusammenhängend. Daher gibt es Gerüste T_{1},...,T_{M} von S_{1}(e_{0}),...,S_{M}(e_{0}). Insbesondere ist ρ(T_{i}) = 0 für jedes i = 1,...,M. Nun verbinde man e_{0} durch eine Kante k_{1} ∈ K(G) mit T_{1}, T_{1} durch eine Kante k_{2} ∈ K(G) mit T_{2} etc. Durch Hinzunahme der M Kanten k_{1},...,k_{M} zu den Gerüsten T_{1},...,T_{M} erhält man ein Gerüst T von G mit ρ(T) = ∑ _{i=1}^{M} ρ(k_{i}) + ∑ _{i=1}^{M} ρ(T_{i}) = M.

”≥“ Sei b ∈ E(G) mit d(e_{0},b) = max_{x∈E(G)}d(e_{0},x) =: M und T ein beliebiges Gerüst. Dann gibt es einen Weg W in T von e_{0} nach b. Daraus folgt: ρ(T) ≥ ρ(W) ≥ M.

Aufgabe 2.2 Sei G ein schlichter Graph der Ordnung n ≥ 4, und es gelte d(x,G) + d(y,G) ≥ n + 1 für alle paarweise verschiedenen nicht adjazenten Ecken x und y. Zeigen Sie, dass jede Ecke G auf einem Kreis der Länge n − 1 liegt.

Lösung zu Aufgabe 2.2 Sei e ∈ E(G) beliebig und z ∈ E(G) \ {e} beliebig, aber fest. Betrachte G′:= G − {z}. Es ist G′schlicht, n(G′) ≥ 3 und d(x,G′) + d(y,G′) ≥ d(x,G) − 1 + d(y,G) − 1 ≥ n − 1 = n(G′) für alle paarweise verschiedenen (in G′) nicht adjazenten Ecken x und y, denn wenn x und y in G′nicht adjazent sind, so auch nicht in G. Nach dem Satz von Øre ist G′Hamilton’sch. Also gibt es einen Kreis der Länge n − 1 durch e.

Aufgabe 2.3 Es seien x_{1},x_{2},...,x_{n} die Ecken eines n-Turnieres T_{n}.

a) Beweisen Sie ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}) ≥ \binom{p}{2} für alle p = 1,2,...,n.

b) Es sei n ≥ 3 und T_{n} stark zusammenhängend. Beweisen Sie ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}) ≥ \binom{p}{2} + 1 für alle p = 1,2,...,n − 1.

Lösung zu Aufgabe 2.3 a) T_{n}^{(p)} := T_{n}− {x_{p+1} ,...,x_{n}} ist wieder ein Turnier der Ordnung p. Daher folgt: ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}) ≥ ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}^{(p)}) = \binom{p}{2}.

b) Sei p ∈ {1,...,n − 1}. Da T_{n} stark zusammenhängend, kann {x_{1},...,x_{p}} nicht {x_{p+1} ,...,x_{n}} dominieren. Also gibt es einen Bogen x_{i}x_{j} ∈ B(T_{n}) für ein i ≤ p und j > p. Daher folgt wie oben: ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}) ≥ ∑ _{i=1}^{p} d^{+} (x_{i},T_{n}^{(p)}) + 1 = \binom{p}{2} + 1.

Aufgabe 2.4 Sei G ein schlichter, zusammenhängender Graph der Ordnung n(G) = 2p mit p ∈ ℕ, welcher ein perfektes Matching M enthält. Weiter gilt, dass jede Kante k ∈ M eine Brücke von G ist.

a) Zeigen Sie: m(G) ≤ \binom{p+1}{2}. (⋆)

b) Geben Sie im Fall p = 4 einen Graphen an, für den in der (⋆)-Ungleichung die Gleichheit gilt.

Lösung zu Aufgabe 2.4 a) Man gehe vom Graphen G zu einem Graphen G′über, indem man alle Ecken x,y ∈ E(G) mit xy ∈ M paarweise zusammenschrumpft und die hierdurch resultierenden p Schlingen eliminiert. Der hierdurch entstandene Multigraph G′hat genau p Kanten und p Ecken weniger als G. Tatsächlich ist G′ sogar schlicht, denn Mehrfachkanten hätten nur von Dreikreisen entstehen können, die eine Kante von M enthalten würden, was nach Voraussetzung nicht der Fall ist. Also gilt: m(G) = m(G′) + p ≤ \binom{n(G′)}{2} + p = \binom{p}{2} + p = \binom{p+1}{2}.

b) Man zeichne einen K_{4} und hänge an jede der vier Ecken je einen Stachel.

Aufgabe 2.5 Sei G ein schlichter, zusammenhängender Graph mit folgenden Eigenschaften: G besitzt einen 2-Faktor F und μ(G) = 3.

a) Sei a eine Ecke von G mit d(a,G) =: p ≥ 2. Wie viele Nachbarn x mit d(x,G) ≥ 3 besitzt a mindestens?

b) Bestimmen Sie die möglichen Werte von τ_{p}(G) für alle p ≠ 2. Dabei ist τ_{p}(G) die Anzahl der Ecken vom Grade p in G.

c) Skizzieren Sie ein nicht-Hamilton’sches Modell minimaler Ordnung.

Lösung zu Aufgabe 2.5 ist dringend gesucht!

Aufgabe 2.6 Sei G ein schlichter, zusammenhängender und 1-faktorisierbarer Graph mit n(G) ≥ 4.

a) Zeigen Sie, dass G keine Brücke enthält.

b) Zeigen Sie, dass G nicht selbstkomplementär ist.

Lösung zu Aufgabe 2.6 a) Da G 1-faktorisierbar, ist G ein r-regulärer Graph. Für gerades r ist G Euler’sch und kann somit keine Brücken besitzen. Angenommen, G besäße eine Brücke k ∈ K(G). Dann ist r ≥ 3 ungerade. Es seien K_{1},K_{2} die beiden Zusammenhangskomponenten von G − k, welche jeweils aus mindestens r Ecken bestehen. Nach dem Handschlaglemma ist n(K_{1}) ungerade, weil alle Ecken von K_{1} bis auf eine in K_{1} den ungeraden Grad r haben. Wähle nun einen 1-Faktor F von G, der k nicht enthält. Dann enthält F nur Kanten in K_{1} oder in K_{2}. Indem man alle Kanten in K_{2} eliminiert, erhält man einen 1-Faktor von K_{1}, was dem Handschlaglemma widerspricht, weil n(K_{1}) ungerade ist.

b) Angenommen, G wäre dennoch selbstkomplementär. Der Komplementärgraph ist offenbar (n(G) − 1 − r)-regulär. Also muss r = n(G) − 1 − r bzw. r = \frac{n(G)−1}{2} gelten. Dann ist also n(G) ungerade. Nach dem Handschlaglemma kann G dann aber keine 1-Faktoren besitzen.

3 Scheinklausur am 17. 7. 2003

Aufgabe 3.1 Es sei G ein schlichter und zusammenhängender Graph mit einer Schnittecke u. Beweisen oder widerlegen Sie:

a) Der Komplementärgraph \overline{G}ist zusammenhängend.

b) u ist keine Schnittecke von \overline{G}.

c) Aus d(u,G) ≤ n(G) − 2 folgt dm(\overline{G}) ≤ 3.

Lösung zu Aufgabe 3.1 a) Diese Aussage ist falsch. Als Gegenbeispiel wähle man einen Weg der Länge 3.

b) Diese Aussage ist richtig. Es seien G_{1},G_{2},...,G_{p}, p ≥ 2 die Zusammenhangskomponenten von G − u. Dann ist \overline{G}[E(G) − \{u\}] zusammenhängend, denn aus x ∈ E(G_{i}) und y ∈ E(G_{j}) mit i ≠ j folgt xy ∈ K(\overline{G}), und aus x,y ∈ E(G_{i}) und z ∈ E(G_{j}) mit i ≠ j folgt xz,zy ∈ E(\overline{G}).

c) Diese Aussage ist richtig. Angenommen, es gilt dm(\overline{G}) ≥ 4. Dann folgt aus Satz 1.15 dm(G) ≤ 2. Wegen d(u,G) ≤ n(G) − 2 existiert eine Ecke w, die zu u nicht adjazent ist. Ist ohne Einschränkung w ∈ E(G_{1}), so ist der Abstand von w zu jeder Ecke y aus G_{2} mindestens 3 im Widerspruch zu dm(G) ≤ 2.

Aufgabe 3.2 Es sei G ein schlichter zusammenhängender Kaktusgraph mit n ≥ 3 Ecken.

a) Zeigen Sie: G ist Hamilton’sch ⇔ G ist ein Kreis.

b) Sei μ(G) = \frac{n−1}{2} . Beweisen Sie zunächst, dass m(G) = 3ν(G) gilt, und zeigen Sie dann, dass G Euler’sch ist.

Lösung zu Aufgabe 3.2 a) ”⇐“ Ist G ein Kreis, so ist G logischerweise Hamilton’sch.

”⇒“ Sei G Hamilton’sch. Dann enthält G einen Kreis C = x_{1}··· x_{n}x_{1} durch alle n Ecken von G. Angenommen, es wäre G ≠ C. Dann ist K(G) \ K(C) ≠ ∅. Sei also k =: x_{i}x_{j} ∈ K(G) \ K(C). Dann befindet sich k in den zwei Kreisen x_{j}x_{j+1} ··· x_{i−1} x_{i}x_{j} und x_{i}x_{i+1} ··· x_{j−1} x_{j}x_{i} (alle Indizes sind modulo n zu verstehen), ein Widerspruch zu Satz 2.5.

b) Nach der Definition von Kaktusgraphen und der zyklomatischen Zahl μ gilt: ν(G) = μ(G) = \frac{n−1}{2} = m − n + 1, also m = 3\frac{n−1}{2} = 3ν.

Da jeder Kreis 3 Kanten enthält und in Kaktusgraphen nach Satz 2.5 alle Kreise kantendisjunkt sind, gilt offensichtlich m(G) ≥ 3ν(G). Gleichheit kann nur gelten, falls G eine Vereinigung von kantendisjunkten Kreisen der Länge 3 ist. Da G zusammenhängend ist, folgt nach Satz 3.2 die Behauptung.

Aufgabe 3.3 Es sei D ein c-partites Turnier c ≥ 2 der Ordnung n, und es sei

i_{g} = max{d^{+} (x,D),d^{−} (x,D) | x ∈ E(D)} − min{d^{+} (x,D),d^{−} (x,D) | x ∈ E(D)}.

Ferner seien V_{1},V_{2},...,V_{c} die Partitionsmengen von D, so dass 1 ≤ r = |V_{1}| ≤ |V_{2}| ≤ ···≤ |V_{c}| = r + 2i_{g} gilt. Für eine Ecke x ∈ E(D) sei V (x) die Partitionsmenge V_{i} mit x ∈ V_{i}.

a) Zeigen Sie, dass n − r gerade ist.

b) Sei i_{g} = 1. Zeigen Sie die folgende Verbesserung von Übung 6, Aufgabe 5:

d^{+} (x),d^{−} (x) = \{ \begin{matrix}\frac{n−r−2}{2} , & wenn & |V (x)| = r + 2, \\ \frac{n−r}{2} , & wenn & |V (x)| = r. \end{matrix}

Lösung zu Aufgabe 3.3 a) Angenommen, n − r ist ungerade. Seien x_{1} ∈ V_{1} und x_{c} ∈ V_{c}. Dann folgt d^{+} (x_{1}) + d^{−} (x_{1}) = n − r und d^{+} (x_{c})+d^{−} (x_{c}) = n−r −2i_{g}. Sei ohne Einschränkung d^{+} (x_{1}) ≥ d^{−} (x_{1}) und d^{+} (x_{c}) ≥ d^{−} (x_{c}). Da n − r (und damit auch n − r − 2i_{g}) ungerade ist, folgern wir, dass d^{+} (x_{1}) ≥ \frac{n−r+1}{2} und d^{−} (x_{c}) ≤ \frac{n−r−2i_{g}−1}{2} . Insgesamt haben wir den Widerspruch d^{+} (x_{1}) − d^{−} (x_{c}) ≥ \frac{n−r+1}{2} − \frac{n−r−2i_{g}−1}{2} = i_{g}+ 1.

b) Laut Übung 6, Aufgabe 5 gilt für Ecken x_{1} und x_{2} mit |V (x_{1})| = r +2 und |V (x_{2})| = r, dass \frac{n−r−3}{2} ≤ d^{+} (x_{1}),d^{−} (x_{1}) ≤ \frac{n−r−1}{2} und \frac{n−r−1}{2} ≤ d^{+} (x_{2}),d^{−} (x_{2}) ≤ \frac{n−r+1}{2} . Da n−r nach a) gerade ist, schließen wir aus der Ganzzahligkeit der Eckengrade, dass d^{+} (x_{1}),d^{−} (x_{1}) = \frac{n−r−2}{2} und d^{+} (x_{2}),d^{−} (x_{2}) = \frac{n−r}{2} .

Aufgabe 3.4 Bestimmen Sie die Anzahl der verschiedenen perfekten Matchings im vollständigen Graphen K_{2n}.

Lösung zu Aufgabe 3.4 Da jeder Die gesuchte Anzahl ist 1 · 3 · 5··· (2n − 1) = ∏ _{i=0}^{n−1} (2i + 1). Beweis durch vollständige Induktion nach n, wobei der Induktionsanfang n = 1 natürlich richtig ist. Nun sei n ≥ 2 und u eine beliebige Ecke des K_{2n}. Weiter seien x_{1},...,x_{2n−1} die verbleibenden Ecken. Nun ist G_{i} := K_{2n}− {u,x_{i}},1 ≤ i ≤ 2n − 1 der vollständige Graph K_{2n−2} , der nach Induktionsvoraussetzung 1 · 3 · 5··· (2n − 3) perfekte Matchings besitzt. Damit besitzt der K_{2n} genau 1 · 3··· (2n − 3) perfekte Matchings, die die Kante ux_{i} enthalten für 1 ≤ i ≤ 2n − 1. Insgesamt besitzt der K_{2n} also 1 · 3··· (2n − 3) · (2n − 1) = ∏ _{i=0}^{n−1} (2i + 1) verschiedene perfekte Matchings.