\section{Chromatische Zahl}
\begin{tasks}
	\item
		Angenommen der Graph $G$ ist vollständig. So hat jeder Knoten den maximalen
		Knotengrad $\Delta(G)$. Für alle Knoten $v$ gilt, dass jeder adjazente
		Knoten und $v$ eine eigene Farbe haben muss. Das sind also $\Delta(G) + 1$
		viele. Jeder Graph (mit weniger Kanten) hat also eine chromatische Zahl
		$\chi(G) \leq \Delta(G) + 1$.
		\points{2}
	
	\item
		Für alle Anzahlen an Knoten $n \in \NN$ und Maximalgrad $\Delta < n$ existiert ein
		Graph $G_{n,\Delta}$ mit $\chi(G_{n,\Delta}) = \Delta + 1$. Dieser Graph
		hat eine Clique der Größe $\Delta$.
		\points{2}
	
	\item
		\begin{align*}
			& \text{Variablen:} & x_1, \dots, x_{n} \in \set{1, \dots, \Delta + 1} \\
			&&\text{Jeder Knoten hat eine Farbe} \\ 
			& \text{Zielfunktion:} & \argmin \sum_{i=1}^{n} x_i \\
			&&\text{Es werden so wenig Farben wie möglich benutzt} \\ 
			& \text{Nebenbedingung:} & \forall ab \colon x_a \neq x_b \\
			&&\text{Die Knoten einer Kante haben nicht die selbe Farbe}
		\end{align*}
		\points{2}
	
	\item
		Wir führen eine binäre Hilfvariable ein:
		\[
			y = \begin{cases}
				1 & \text{falls } x_1 \leq x_2 - 1 \text{ oder } x_1 - 1 \geq x_2 \\
				0 & \text{sonst}
			\end{cases}
		\]
		Die Konstante $M$ stellt sicher, dass wir nicht in die Situation $\infty - 1$
		kommen, was nicht definiert ist.

		Nun können wir $x_1 \neq x_2$ durch $y = 1$ ersetzen.
		\points{3}
	
\end{tasks}