\documentclass{uebungsblatt}
\usepackage{tikz}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{13}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 4 -- 5
  \draw [] (179bp,252bp) .. controls (186bp,260bp) and (194bp,269bp)  .. (201bp,276bp);
  % Edge: 8 -- 2
  \draw [] (160bp,76bp) .. controls (150bp,80bp) and (140bp,85bp)  .. (130bp,89bp);
  % Edge: 2 -- 3
  \draw [] (107bp,116bp) .. controls (108bp,130bp) and (108bp,150bp)  .. (109bp,164bp);
  % Edge: 7 -- 2
  \draw [] (103bp,37bp) .. controls (104bp,50bp) and (105bp,67bp)  .. (106bp,80bp);
  % Edge: 1 -- 2
  \draw [] (53bp,84bp) .. controls (62bp,86bp) and (73bp,89bp)  .. (82bp,91bp);
  % Edge: 3 -- 4
  \draw [] (124bp,197bp) .. controls (132bp,205bp) and (142bp,214bp)  .. (150bp,222bp);
  % Edge: 6 -- 3
  \draw [] (61bp,215bp) .. controls (70bp,209bp) and (81bp,201bp)  .. (90bp,195bp);
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (28bp,77bp) ellipse (27bp and 18bp);
  \draw (28bp,77bp) node {1};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (109bp,182bp) ellipse (27bp and 18bp);
  \draw (109bp,182bp) node {3};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (107bp,98bp) ellipse (27bp and 18bp);
  \draw (107bp,98bp) node {2};
\end{scope}
  % Node: 5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (216bp,292bp) ellipse (27bp and 18bp);
  \draw (216bp,292bp) node {5};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (165bp,237bp) ellipse (27bp and 18bp);
  \draw (165bp,237bp) node {4};
\end{scope}
  % Node: 7
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (102bp,19bp) ellipse (27bp and 18bp);
  \draw (102bp,19bp) node {7};
\end{scope}
  % Node: 6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (42bp,228bp) ellipse (27bp and 18bp);
  \draw (42bp,228bp) node {6};
\end{scope}
  % Node: 8
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (183bp,67bp) ellipse (27bp and 18bp);
  \draw (183bp,67bp) node {8};
\end{scope}
%
\end{tikzpicture}


Der Graph B hat den Prüfer-Code 2, 4, 3, 3, 2, 2 der zustande kommt, wenn man
den kleinsten Knoten vom Grad 1 streicht und den anderen, übrig gebliebenen
Knoten in den Prüfer-Code einfügt und dann so lange wiederholt, bis nur noch
zwei Knoten übrig sind.

\teilaufgabe

Um den Prüfer-Code 2, 3, 4, 3, 2 in einen Graphen zurückzuführen kann man den
Algorithmus aus Steger, Diskrete Strukturen, Band 1, Kapitel 2.2 verwenden.
Dazu macht man sich bewusst, dass die Knotenmenge die Knoten 1, 2, 3, 4, 5, 6,
7 enthält (Länge des Prüfer-Codes + 2). Nun führt man die Schleifenschritte
durch:

\begin{enumerate}
  \item $i = 1$: $t_1 = 2$ $s_1 = 1$ $S = \{1\}$ $\rightarrow \{1, 2\}$
  \item $i = 2$: $t_2 = 3$ $s_2 = 5$ $S = \{1, 5\}$ $\rightarrow \{3, 5\}$
  \item $i = 3$: $t_3 = 4$ $s_3 = 6$ $S = \{1, 5, 6\}$ $\rightarrow \{4, 6\}$
  \item $i = 4$: $t_4 = 3$ $s_4 = 4$ $S = \{1, 4, 5, 6\}$ $\rightarrow \{3, 4\}$
  \item $i = 5$: $t_5 = 2$ $s_5 = 5$ $S = \{1, 3, 4, 5, 6\}$ $\rightarrow \{2, 5\}$
  \item Rest: $\{2, 7\}$
\end{enumerate}

Somit wären das die Kanten des Graphen. Dieser Graph kann nun konstruiert
werden:

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 2 -- 3
  \draw [] (105bp,105bp) .. controls (108bp,118bp) and (113bp,135bp)  .. (116bp,147bp);
  % Edge: 4 -- 6
  \draw [] (210bp,214bp) .. controls (217bp,219bp) and (225bp,225bp)  .. (233bp,231bp);
  % Edge: 2 -- 7
  \draw [] (110bp,70bp) .. controls (117bp,60bp) and (125bp,46bp)  .. (131bp,36bp);
  % Edge: 3 -- 4
  \draw [] (142bp,176bp) .. controls (151bp,181bp) and (161bp,186bp)  .. (169bp,190bp);
  % Edge: 1 -- 2
  \draw [] (51bp,66bp) .. controls (59bp,70bp) and (69bp,74bp)  .. (77bp,77bp);
  % Edge: 3 -- 5
  \draw [] (105bp,180bp) .. controls (97bp,188bp) and (87bp,198bp)  .. (79bp,207bp);
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (28bp,56bp) ellipse (27bp and 18bp);
  \draw (28bp,56bp) node {1};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (120bp,165bp) ellipse (27bp and 18bp);
  \draw (120bp,165bp) node {3};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (100bp,87bp) ellipse (27bp and 18bp);
  \draw (100bp,87bp) node {2};
\end{scope}
  % Node: 5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (64bp,222bp) ellipse (27bp and 18bp);
  \draw (64bp,222bp) node {5};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (191bp,201bp) ellipse (27bp and 18bp);
  \draw (191bp,201bp) node {4};
\end{scope}
  % Node: 7
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (142bp,19bp) ellipse (27bp and 18bp);
  \draw (142bp,19bp) node {7};
\end{scope}
  % Node: 6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (251bp,244bp) ellipse (27bp and 18bp);
  \draw (251bp,244bp) node {6};
\end{scope}
%
\end{tikzpicture}

\teilaufgabe

Man erkennt dass der Prüfer-Code einen Pfad beschreibt daran, dass jeder Knoten
nur ein mal im Code vorkommt. Das liegt daran, dass ein Pfad nur Knoten vom
Grad 1 (Endpunkte, zwei Stück) oder Knoten vom Grad 2 enthält (Mittelstücke,
Länge des Pfades - 2 Stück). Die Knoten vom Grad 1 werden im Prüfer-Code gar
nicht aufgenommen, da bei der Konstruktion des Prüfer-Codes prinzipiell nur die
Knoten aufgenommen werden, an denen noch weitere Knoten hängen. Die Knoten vom
Grad 2 kommen nur ein mal vor, denn nachdem einer der an ihnen hängenden Knoten
entfernt wurde und sie im Prüfer-Code aufgezeichnet wurden, sie nur noch vom
Grad 1 sind und somit nicht noch einmal in den Code aufgenommen werden.

\aufgabe

\teilaufgabe

Fast-4-regulär, das bedeutet, dass 4 Knoten  den Grad 2 haben, der Rest den
Grad 4 hat. In einem Graphen G mit 6 Knoten bedeutet das, dass es 4 Knoten vom
Grad 2 gibt und 2 Knoten vom Grad vier. Es gibt für diesen Graphen tatsächlich
nur eine Möglichkeit:

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 3 -- 6
  \draw [] (49bp,79bp) .. controls (76bp,65bp) and (122bp,42bp)  .. (149bp,29bp);
  % Edge: 4 -- 5
  \draw [] (99bp,72bp) .. controls (99bp,61bp) and (99bp,47bp)  .. (99bp,36bp);
  % Edge: 4 -- 6
  \draw [] (114bp,75bp) .. controls (126bp,63bp) and (143bp,46bp)  .. (156bp,33bp);
  % Edge: 1 -- 6
  \draw [] (171bp,72bp) .. controls (171bp,61bp) and (171bp,47bp)  .. (171bp,36bp);
  % Edge: 1 -- 5
  \draw [] (156bp,75bp) .. controls (144bp,63bp) and (127bp,46bp)  .. (114bp,33bp);
  % Edge: 2 -- 6
  \draw [] (228bp,75bp) .. controls (216bp,63bp) and (199bp,46bp)  .. (186bp,33bp);
  % Edge: 2 -- 5
  \draw [] (221bp,79bp) .. controls (194bp,65bp) and (148bp,42bp)  .. (121bp,29bp);
  % Edge: 3 -- 5
  \draw [] (42bp,75bp) .. controls (54bp,63bp) and (71bp,46bp)  .. (84bp,33bp);
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (171bp,90bp) ellipse (27bp and 18bp);
  \draw (171bp,90bp) node {1};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,90bp) ellipse (27bp and 18bp);
  \draw (27bp,90bp) node {3};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (243bp,90bp) ellipse (27bp and 18bp);
  \draw (243bp,90bp) node {2};
\end{scope}
  % Node: 5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,18bp) ellipse (27bp and 18bp);
  \draw (99bp,18bp) node {5};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,90bp) ellipse (27bp and 18bp);
  \draw (99bp,90bp) node {4};
\end{scope}
  % Node: 6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (171bp,18bp) ellipse (27bp and 18bp);
  \draw (171bp,18bp) node {6};
\end{scope}
%
\end{tikzpicture}

Die erste, obere Partition besteht aus vier Knoten vom Grad 2, die
logischerweise mit 2 Knoten aus der unteren Partition verbunden sein müssen,
somit ist jeder Knoten der oberen Partition mit den Knoten aus der unteren
Partition verbunden. Gleichzeitig muss es zwei Knoten vom Grad vier geben. In
diesem Graphen sind das die Knoten 5 und 6, die, da sie beide Grad 4 haben
müssen, somit zwangsweise mit jedem Knoten aus der oberen Menge verbunden sind.
Es gibt keine anderen Möglichkeiten die Bipartition anzulegen, da die Knoten
vom Grad 4 alleine in einer Partition sein müssen, damit sie vier Knoten zum
verbinden in der anderen Partition haben.

Dieser Graph ist planar (leider nicht in der Darstellung von \texttt{dot}, da
muss man sich die Kanten die innen verlaufen außenrum vorstellen, was auf jeden
Fall möglich ist) da nach dem Satz von Kuratowski der vorliegende $K_{4,2}$
weder eine Unterteilung des $K_{3,3}$ als Teilgraphen enthält (da eine
Partition nur 2 Knoten enthält und somit so ein Teilgraph nicht möglich ist)
noch eine Unterteilung des $K_5$ enthält (da der Graph bipartit ist und somit
keinen vollständigen Graphen $\geq K_5$ enthalten kann).

\teilaufgabe

Induktionsbasis ist $n_0 = 1$, da bewiesen werden muss, dass die Aussage für
alle Graphen mit $n \geq 1$ gilt. Da $n_0 = 1$ ist die Mächtigkeit der Menge A
$|A| = 2 \cdot n_0 = 2 = |B|$, somit enthalten A und B jeweils zwei Knoten. Der
Graph hat also 4 Knoten, davon 4 vom Grad zwei und 0 vom Grad 4. Solch ein
Graph ist trivial herzustellen, siehe Abbildung in Aufgabe 3.2. Natürlich kann
man solch einen Graphen auch planar darstellen.

Bei dem Induktionsschritt $n + 1$ ist $|A| = 2 \cdot (n + 1) = |B|$.
Verglichen zum Fall von $n$ kommen nun auf jeder Seite zwei weitere Knoten hinzu,
insgesamt 4. Diese vier neuen Knoten werden so verbunden, dass sie den
Grad 2 bekommen und die vorherigen Knoten vom Grad 2 werden zu Knoten von
Grad 4. Die Zeichnung demonstriert das für den Graphen $G_{n+1}$ wobei die
alten Knoten mit $a$ bezeichnet sind und die neu hinzugefügten mit $n$.

\begin{tikzpicture}[>=latex,join=bevel,scale=.8]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 3 -- 6
  \draw [] (121bp,79bp) .. controls (148bp,65bp) and (194bp,42bp)  .. (221bp,29bp);
  % Edge: 3 -- 11
  \draw [] (84bp,75bp) .. controls (72bp,63bp) and (55bp,46bp)  .. (42bp,33bp);
  % Edge: 4 -- 5
  \draw [] (171bp,72bp) .. controls (171bp,61bp) and (171bp,47bp)  .. (171bp,36bp);
  % Edge: 3 -- 12
  \draw [] (99bp,72bp) .. controls (99bp,61bp) and (99bp,47bp)  .. (99bp,36bp);
  % Edge: 10 -- 8
  \draw [] (444bp,75bp) .. controls (432bp,63bp) and (415bp,46bp)  .. (402bp,33bp);
  % Edge: 4 -- 11
  \draw [] (149bp,79bp) .. controls (122bp,65bp) and (76bp,42bp)  .. (49bp,29bp);
  % Edge: 4 -- 6
  \draw [] (186bp,75bp) .. controls (198bp,63bp) and (215bp,46bp)  .. (228bp,33bp);
  % Edge: 1 -- 6
  \draw [] (243bp,72bp) .. controls (243bp,61bp) and (243bp,47bp)  .. (243bp,36bp);
  % Edge: 4 -- 12
  \draw [] (156bp,75bp) .. controls (144bp,63bp) and (127bp,46bp)  .. (114bp,33bp);
  % Edge: 9 -- 8
  \draw [] (387bp,72bp) .. controls (387bp,61bp) and (387bp,47bp)  .. (387bp,36bp);
  % Edge: 1 -- 7
  \draw [] (258bp,75bp) .. controls (270bp,63bp) and (287bp,46bp)  .. (300bp,33bp);
  % Edge: 10 -- 7
  \draw [] (437bp,79bp) .. controls (410bp,65bp) and (364bp,42bp)  .. (337bp,29bp);
  % Edge: 2 -- 8
  \draw [] (330bp,75bp) .. controls (342bp,63bp) and (359bp,46bp)  .. (372bp,33bp);
  % Edge: 2 -- 7
  \draw [] (315bp,72bp) .. controls (315bp,61bp) and (315bp,47bp)  .. (315bp,36bp);
  % Edge: 1 -- 5
  \draw [] (228bp,75bp) .. controls (216bp,63bp) and (199bp,46bp)  .. (186bp,33bp);
  % Edge: 1 -- 8
  \draw [] (265bp,79bp) .. controls (292bp,65bp) and (338bp,42bp)  .. (365bp,29bp);
  % Edge: 2 -- 6
  \draw [] (300bp,75bp) .. controls (288bp,63bp) and (271bp,46bp)  .. (258bp,33bp);
  % Edge: 9 -- 7
  \draw [] (372bp,75bp) .. controls (360bp,63bp) and (343bp,46bp)  .. (330bp,33bp);
  % Edge: 2 -- 5
  \draw [] (293bp,79bp) .. controls (266bp,65bp) and (220bp,42bp)  .. (193bp,29bp);
  % Edge: 3 -- 5
  \draw [] (114bp,75bp) .. controls (126bp,63bp) and (143bp,46bp)  .. (156bp,33bp);
  % Node: 11
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,18bp) ellipse (27bp and 18bp);
  \draw (27bp,18bp) node {n};
\end{scope}
  % Node: 10
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (459bp,90bp) ellipse (27bp and 18bp);
  \draw (459bp,90bp) node {n};
\end{scope}
  % Node: 12
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,18bp) ellipse (27bp and 18bp);
  \draw (99bp,18bp) node {n};
\end{scope}
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (243bp,90bp) ellipse (27bp and 18bp);
  \draw (243bp,90bp) node {a};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,90bp) ellipse (27bp and 18bp);
  \draw (99bp,90bp) node {a};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (315bp,90bp) ellipse (27bp and 18bp);
  \draw (315bp,90bp) node {a};
\end{scope}
  % Node: 5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (171bp,18bp) ellipse (27bp and 18bp);
  \draw (171bp,18bp) node {a};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (171bp,90bp) ellipse (27bp and 18bp);
  \draw (171bp,90bp) node {a};
\end{scope}
  % Node: 7
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (315bp,18bp) ellipse (27bp and 18bp);
  \draw (315bp,18bp) node {a};
\end{scope}
  % Node: 6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (243bp,18bp) ellipse (27bp and 18bp);
  \draw (243bp,18bp) node {a};
\end{scope}
  % Node: 9
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (387bp,90bp) ellipse (27bp and 18bp);
  \draw (387bp,90bp) node {n};
\end{scope}
  % Node: 8
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (387bp,18bp) ellipse (27bp and 18bp);
  \draw (387bp,18bp) node {a};
\end{scope}
%
\end{tikzpicture}

\aufgabe

\teilaufgabe

Ein Graph mit $n = 6$ Knoten, $(n - 2) = 4$-regulär:

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 3 -- 6
  \draw [] (78bp,144bp) .. controls (85bp,116bp) and (98bp,64bp)  .. (105bp,36bp);
  % Edge: 5 -- 6
  \draw [] (44bp,75bp) .. controls (58bp,63bp) and (78bp,45bp)  .. (93bp,32bp);
  % Edge: 4 -- 6
  \draw [] (130bp,73bp) .. controls (126bp,61bp) and (120bp,47bp)  .. (116bp,35bp);
  % Edge: 3 -- 5
  \draw [] (63bp,145bp) .. controls (55bp,134bp) and (45bp,118bp)  .. (38bp,107bp);
  % Edge: 1 -- 4
  \draw [] (132bp,224bp) .. controls (149bp,215bp) and (172bp,200bp)  .. (182bp,180bp) .. controls (189bp,165bp) and (187bp,159bp)  .. (182bp,144bp) .. controls (176bp,128bp) and (164bp,114bp)  .. (154bp,104bp);
  % Edge: 3 -- 4
  \draw [] (88bp,146bp) .. controls (98bp,134bp) and (112bp,118bp)  .. (123bp,106bp);
  % Edge: 1 -- 5
  \draw [] (88bp,223bp) .. controls (72bp,214bp) and (50bp,199bp)  .. (38bp,180bp) .. controls (25bp,158bp) and (24bp,127bp)  .. (25bp,108bp);
  % Edge: 2 -- 6
  \draw [] (158bp,146bp) .. controls (169bp,127bp) and (184bp,96bp)  .. (173bp,72bp) .. controls (164bp,53bp) and (145bp,38bp)  .. (130bp,29bp);
  % Edge: 1 -- 2
  \draw [] (119bp,217bp) .. controls (124bp,205bp) and (132bp,191bp)  .. (137bp,179bp);
  % Edge: 2 -- 5
  \draw [] (126bp,150bp) .. controls (104bp,136bp) and (69bp,115bp)  .. (47bp,102bp);
  % Edge: 1 -- 3
  \draw [] (101bp,217bp) .. controls (96bp,205bp) and (88bp,191bp)  .. (83bp,179bp);
  % Edge: 2 -- 4
  \draw [] (144bp,144bp) .. controls (142bp,133bp) and (141bp,119bp)  .. (139bp,108bp);
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (110bp,234bp) ellipse (27bp and 18bp);
  \draw (110bp,234bp) node {1};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (74bp,162bp) ellipse (27bp and 18bp);
  \draw (74bp,162bp) node {3};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (146bp,162bp) ellipse (27bp and 18bp);
  \draw (146bp,162bp) node {2};
\end{scope}
  % Node: 5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,90bp) ellipse (27bp and 18bp);
  \draw (27bp,90bp) node {5};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (137bp,90bp) ellipse (27bp and 18bp);
  \draw (137bp,90bp) node {4};
\end{scope}
  % Node: 6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (109bp,18bp) ellipse (27bp and 18bp);
  \draw (109bp,18bp) node {6};
\end{scope}
%
\end{tikzpicture}

\teilaufgabe

Die chromatische Zahl $\chi = \frac{n}{2}$ bedeutet, dass maximal $\frac{n}{2}$
Farben nötig sind, um einen Graphen mit $n$ Knoten zu färben. Gleichzeitig
bedeutet es aber auch, dass die Knoten des Graphen in $\frac{n}{2}$
Partititionen eingeteilt werden können. Um zu zeigen, dass diese Bedingung für
alle geraden $n \in \N$ zutrifft, wird im folgenden gezeigt, wie solch ein
Graph konstruiert werden kann.

Der Basisfall ist der Graph $n = 4$, der in $\frac{4}{2} = 2$ Partitionen geteilt wird:

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: 2 -- 3
  \draw [] (84bp,75bp) .. controls (72bp,63bp) and (55bp,46bp)  .. (42bp,33bp);
  % Edge: 1 -- 4
  \draw [] (42bp,75bp) .. controls (54bp,63bp) and (71bp,46bp)  .. (84bp,33bp);
  % Edge: 1 -- 3
  \draw [] (27bp,72bp) .. controls (27bp,61bp) and (27bp,47bp)  .. (27bp,36bp);
  % Edge: 2 -- 4
  \draw [] (99bp,72bp) .. controls (99bp,61bp) and (99bp,47bp)  .. (99bp,36bp);
  % Node: 1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,90bp) ellipse (27bp and 18bp);
  \draw (27bp,90bp) node {1};
\end{scope}
  % Node: 3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,18bp) ellipse (27bp and 18bp);
  \draw (27bp,18bp) node {3};
\end{scope}
  % Node: 2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,90bp) ellipse (27bp and 18bp);
  \draw (99bp,90bp) node {2};
\end{scope}
  % Node: 4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (99bp,18bp) ellipse (27bp and 18bp);
  \draw (99bp,18bp) node {4};
\end{scope}
%
\end{tikzpicture}

Man sieht, dass dieser Graph bipartit ist und alle Knoten den Grad $(n - 2) =
2$ haben. Nun wird der Schritt von $n$ zu $n + 2$ gemacht (da $n$ gerade sein
soll, müssen immer zwei neue Knoten hinzugefügt werden). Dazu wird der Graph
für $n$ um die zwei neu hinzukommenden Knoten erweitert, die in eine eigene
Partition geteilt werden. Diese haben erstmal den Grad null, müssen also noch
mit den allen $n$ Knoten des alten Graphen verbunden werden, dadurch haben sie
Grad $n$ (was der Vorraussetzung entspricht, denn $((n + 2) - 2) = n$.  Durch
die 2 neuen Kanten pro Knoten des alten Graphen steigt auch deren Kantenanzahl
auf $n$, somit haben alle $n + 2$ Knoten des neuen, erweiterten Graphen Grad
$n$ und erfüllen die Bedingung dass der Graph regulär ist und der Grad der
Kanten gleich der Anzahl der Knoten minus 2 ist.  Zusätzlich ist auch die
Anzahl der Partitionen immer gleich $\frac{\text{Anzahl der Knoten}}{2}$ da für
jeden Schritt, der zwei Knoten dem Graphen hinzufügt, eine neue Partition
entsteht. Dies bedeutet auch, dass auch allgemein $\chi = \frac{n}{2}$ gilt, da
dieser neue Graph auch wieder um zwei weitere Knoten erweitert werden kann
unter Beibehaltung der geforderten Eigenschaften.

\aufgabe

Die Gradfolge des resultierende Stammbaumes ist $1, (2 \cdot n - 2) \cdot 2,
1$. Das erklärt sich darin, wie die Tiefensuche funktioniert: man geht von
einem Startpunkt aus und geht von dort zu dem Knoten mit der kleinsten Zahl.
Somit ist der Grad des Startpunktes 1. Nun läuft der Algorithmus von Knoten zu
dem jeweils kleinsten nächsten möglichen Knoten, wobei der Grad jedes Knoten
auf diesem Weg 2 beträgt, da der Knoten einmal betreten und einmal verlassen
wird. Auf diese Weise kann man im bipartiten Graphen jeden Knoten der Reihe
nach betreten indem man von einer zur anderen Partition läuft ohne das Vorgehen
jemals zu ändern (das Verhalten wird nur bei Sackgassen geändert und bei dem
Verfahren gibt es nur am Ende, beim letzten Knoten eine Sackgasse).  Dadurch
wird jeder Knoten genau einmal besucht und man kommt schließlich zu einem
Knoten (der in der jeweils anderen Partition liegt zu der von der man gestartet
ist).  Da man diesen Knoten nur betritt, aber nicht verlässt, hat er Grad 1.
Weitere Unterscheidungen sind nicht mehr nötig, da an diesem Punkt alle Knoten
besucht worden sind und der Spannbaum erstellt werden konnte.

Somit ist die Länge des Spannbaumes des Graphen $K_{n,n} = 2n$, von denen alle
Knoten den Grad 2 haben, bis auf den ersten und letzten.

\end{document}
