%
% chrindprop.tex -- slide template
%
% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
%
\bgroup
\begin{frame}[t]
\setlength{\abovedisplayskip}{5pt}
\setlength{\belowdisplayskip}{5pt}
\frametitle{Zusammenhang zwischen $\operatorname{chr}G$ und $\operatorname{ind}G$}
\vspace{-20pt}
\begin{columns}[t,onlytextwidth]
\begin{column}{0.38\textwidth}
\begin{block}{Proposition}
Ist $G$ ein Graph mit $n$ Knoten, dann gilt
\[
\operatorname{chr}G
\cdot
\operatorname{ind}G
\ge n
\]
\end{block}
\uncover<2->{%
\begin{block}{Beispiel}
Peterson-Graph $K$ hat $n=10$ Knoten:
\[
\operatorname{chr}(K)
\cdot
\operatorname{ind}(K)
=
3\cdot 4
\ge 
10
=
n
\]
\end{block}}
\end{column}
\begin{column}{0.58\textwidth}
\uncover<3->{%
\begin{proof}[Beweis]
\begin{itemize}
\item<4-> eine minimale Färbung hat $\operatorname{chr}(G)$ Farben
\item<5-> Sie teilt die Knoten in $\operatorname{chr}(G)$
gleichfarbige Mengen auf
\item<6-> Jede einfarbige Menge von Knoten ist unabhängig, d.~h.~sie 
besteht aus Knoten, die nicht miteinander verbunden sind.
\item<7-> Jede einfarbige Menge enthält höchstens $\operatorname{ind}(G)$
\item<8-> Die Gesamtzahl der Knoten ist
\[
n\uncover<9->{=\sum_{\text{Farbe}}\underbrace{|V_{\text{Farbe}}|}_{\le \operatorname{ind}(G)}}
\uncover<10->{\le
\operatorname{chr}(G)
\cdot
\operatorname{ind}(G)}
\]
\end{itemize}
\end{proof}}
\end{column}
\end{columns}
\end{frame}
\egroup