\section{Perfektes Eliminationsschema}
\begin{enumerate}
	% \item Kopiere $G$ nach $G$
	\item Falls $\abs{V(G)} = 0$, gib das Eliminationsschema zurück. \label{schritt2}
	\item Suche nach nicht erweiterbaren $U$, sodass $G[U]$ zusammenhängend und $U \cup N(U) \neq V(G)$. Das geht mit Breitensuche mit einem beliebigen Startknoten $s$.
	\item Wähle aus $W = V(G) \setminus U \cup N(U)$ einen Knoten aus und 
		füge ihn zum Eliminationsschema hinzu. Lösche diesen Knoten dann aus $G$.
	\item Gehe zurück zu \autoref{schritt2}.
\end{enumerate}

Das die Menge $U$ nicht maximal sondern nur nicht erweiterbar ist, macht die
Folgerung, dass jeder Knoten in $W$ mit jedem in $N(U)$ verbunden ist, nicht kaputt,
da, wenn es eine Kante zwischen einem Knoten in $N(U)$ und $W$ nicht existiert, $U$
erweitert werden kann.

Ebenfalls bleibt die Eigenschaft, dass $N(U)$ eine Clique ist erhalten. Die Argumentation
ist die selbe, wie zuvor.

Jeder Knoten in $W$ ist ein simplizialer Knoten in $G[W]$, da, wenn es eine Kante
zwischen zwei Knoten in $W$ nicht gibt, dann $U$ erweitert werden kann.

Durch Magie wird nicht der gesamte Breitensuchbaum erstellt und die Breitensuche
läuft in $\oh(\abs{V} + \abs{E}) = \oh(n + n^2)$. Durch die $n$ rekursiven Aufrufe,
in denen jeder Knoten einmal zum Eliminationsschema hinzugefügt wird, Läuft der
ganze Algorithmus läuft dadurch in $\oh(n^3)$
\points{4}