LaTeX-examples/presentations/Diskrete-Mathematik/Plan/Plan.tex

\documentclass[a4paper,9pt]{scrartcl}
\usepackage{amssymb, amsmath} % needed for math
\usepackage[utf8]{inputenc} % this is needed for umlauts
\usepackage[ngerman]{babel} % this is needed for umlauts
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf
\usepackage[margin=2.5cm]{geometry} %layout
\usepackage{hyperref}   % links im text
\usepackage{color}
\usepackage{framed}
\usepackage{enumerate}  % for advanced numbering of lists
\clubpenalty  = 10000   % Schusterjungen verhindern
\widowpenalty = 10000   % Hurenkinder verhindern

\hypersetup{ 
  pdfauthor   = {Martin Thoma}, 
  pdfkeywords = {Diskrete Mathematik}, 
  pdftitle    = {Vortrag Graphentheorie I: Tafelbild + Text} 
} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Custom definition style, by                                       %
% http://mathoverflow.net/questions/46583/what-is-a-satisfactory-way-to-format-definitions-in-latex/58164#58164
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\newdimen\errorsize \errorsize=0.2pt
% Frame with a label at top
\newcommand\LabFrame[2]{%
    \fboxrule=\FrameRule
    \fboxsep=-\errorsize
    \textcolor{FrameColor}{%
    \fbox{%
      \vbox{\nobreak
      \advance\FrameSep\errorsize
      \begingroup
        \advance\baselineskip\FrameSep
        \hrule height \baselineskip
        \nobreak
        \vskip-\baselineskip
      \endgroup
      \vskip 0.5\FrameSep
      \hbox{\hskip\FrameSep \strut
        \textcolor{TitleColor}{\textbf{#1}}}%
      \nobreak \nointerlineskip
      \vskip 1.3\FrameSep
      \hbox{\hskip\FrameSep
        {\normalcolor#2}%
        \hskip\FrameSep}%
      \vskip\FrameSep
    }}%
}}
\definecolor{FrameColor}{rgb}{0.25,0.25,1.0}
\definecolor{TitleColor}{rgb}{1.0,1.0,1.0}

\newenvironment{contlabelframe}[2][\Frame@Lab\ (cont.)]{% 
  % Optional continuation label defaults to the first label plus
  \def\Frame@Lab{#2}%
  \def\FrameCommand{\LabFrame{#2}}%
  \def\FirstFrameCommand{\LabFrame{#2}}%
  \def\MidFrameCommand{\LabFrame{#1}}%
  \def\LastFrameCommand{\LabFrame{#1}}%
  \MakeFramed{\advance\hsize-\width \FrameRestore} 
}{\endMakeFramed} 
\newcounter{definition}
\newenvironment{definition}[1]{%
  \par
  \refstepcounter{definition}%
  \begin{contlabelframe}{Definition \thedefinition:\quad #1}
 \noindent\ignorespaces}
{\end{contlabelframe}} 
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Begin document                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\section{Königsberger Brückenproblem}
\subsection{Beweis des Satzes von Euler}
Tafelbild:

Sie $G = (E, K)$ ein eulerscher Graph, $K$ ein Eulerkreis durch $G$ und 
$e \in E$ eine beliebige Kante.
Dann geht $K$ durch $e$. Nun sei $a$ die Anzahl, wie häufig $K$ durch $e$ geht.
Offensichtlich geht der Kreis sowohl in den Knoten hinein, als auch hinaus.
$\Rightarrow e$ hat mindestens den Knotengrad $2a$. Es kann keine weitere
Kante geben, da jeder Eulerkreis zu $G$ alle Kanten von $G$ beinhaltet.
$\Rightarrow e$ hat den Knotengrad $2a \Rightarrow$ Jede Ecke von $G$ hat geraden
Grad. $\blacksquare$

\subsection{Rückrichtung}
Hat jede Ecke in einem zusammenhängendem Graphen $G$ geraden Grad, so ist $G$ eulerisch.

Beweis durch Induktion über die Anzahl $m$ der Kanten.

\textbf{I.A.}:
\begin{itemize}
    \item $m=0 \rightarrow$ trivial
    \item $m = 1$: nicht möglich
    \item $m = 2$: Da $G$ zusammenhängend ist, können in diesem Fall nur zwei
Ecken zweifach miteinander verbunden sein $\Rightarrow$ auch eulersch
\end{itemize}

\textbf{I.V.}: Sei $m \in \mathbb{N}_{\geq 2}$ die Anzahl der Kanten eines 
Graphs $G$ und jeder zusammenhängende Graph mit weniger als $m$ Kanten und 
ausschließlich Knoten geraden Grades sei eulerisch.

\textbf{I.S.} 

Jeder Knoten hat mindestens Grad 2 (zusammenhängend + gerader Grad)
$\Rightarrow$ es gibt einen Kreis in $G$. TODO

Sei nun $C$ ein Kreis in $G$ mit maximaler Länge.

Annahme: $C$ ist kein Eulerkreis

Wir entfernen alle Kanten in $C$ aus $G$ und nennen das Ergebnis $G^*$.
Dann hat jeder Zusammenhängende Teilgraph in $G^*$ nur Knoten geraden Grades
und hat daher einen Eulerkreis. Dieser Eulerkreis hat keine Kante, die in $C$
enthalten ist und könnte deshalb zu $C$ hinzugefügt werden, wodurch $C$ Länger
werden würde $\Rightarrow$ Widerspruch $\Rightarrow C$ ist ein Eulerkreis
$\Rightarrow G$ ist eulersch  $\blacksquare$
 
\end{document}