% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 16
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die sechzehnte Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} befasst sich wieder mit Snarks.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Snarks, Teil 2}
\end{center}
\normalsize Die Definition von Snarks, die ich in der vorigen Ausgabe brachte, ist zwar g\"{a}ngig, allerdings handelt es sich nicht um jene Definition, die dem Satz ``Es gibt keine planaren Snarks'' zu Grunde liegt. Denn dieser Satz gilt sicher nicht, wenn man Snarks lediglich als zusammenh\"{a}ngende, kubische Graphen ohne Br\"{u}cken definiert, die mit vier Farben f\"{a}rbbar sind. Der Grund: Der $K_4$, also der Graph, der aus vier Knoten besteht, von denen jeder mit jedem anderen Knoten durch eine Kante verbunden ist, w\"{a}re nach dieser Definition ebenfalls ein Snark. Er ist aber planar. Also gilt bei dieser Definition der Satz ``Es gibt keine planaren Snarks'' nicht. Allerdings habe ich nun gelesen, dass normalerweise noch eine zus\"{a}tzliche Bedingung gilt, wann ein Graph ein Snark ist. N\"{a}mlich, dass Snarks einen Kreis von der L\"{a}nge f\"{u}nf oder h\"{o}her enthalten m\"{u}ssen. Damit w\"{a}re der $K_4$ nat\"{u}rlich kein Snark mehr, denn dieser enth\"{a}lt ja \"{u}berhaupt nur vier Knoten.
\\
\\ Im Folgenden werde ich mir \"{u}berlegen, ob es mir gelingt zu beweisen, dass der Satz ``Es gibt keine planaren Snarks'' mit dem Vier-Farben-Satz \"{a}quivalent ist.
\\
\\ Aufgrund der Definition von Snarks haben diese folgende Eigenschaften: $Z$ (zusammenh\"{a}ngend), $K$ (kubisch), $B$ (br\"{u}ckenlos), $N$ (ben\"{o}tigt mindestens vier Farben), $L$ (einen Kreis der L\"{a}nge f\"{u}nf oder h\"{o}her enthaltend). Wenn wir mit $S$ bezeichnen wollen, dass ein Graph ein Snark ist, dann gilt:
\\
\\ $\forall x S(x) \leftrightarrow Z(x) \wedge K(x) \wedge B(x) \wedge V(x) \wedge L(x)$.
\\
\\ Nun gilt, dass jeder Graph, der ein Snark ist, nicht planar ist. Kodieren wir Planarit\"{a}t mit dem Symbol $P$. Es gilt also:
\\
\\ $\forall x S(x) \to \neg P(x)$.
\\
\\ Also:
\\
\\ $\forall x Z(x) \wedge K(x) \wedge B(x) \wedge N(x) \wedge L(x) \to \neg P(x)$.
\\
\\ Dies ist gleichbedeutend mit:
\\
\\ $\forall x P(x) \to \neg (Z(x) \wedge K(x) \wedge B(x) \wedge N(x) \wedge L(x))$,
\\
\\ also
\\
\\ $\forall x P(x) \to \neg Z(x) \vee \neg K(x) \vee \neg B(x) \vee \neg N(x) \vee \neg L(x)$.
\\
\\ Der Vier-Farben-Satz wiederum lautet schlicht und ergreifend ($V$ bedeute, dass ein Graph mit h\"{o}chstens vier Farben gef\"{a}rbt werden kann):
\\
\\ $\forall x P(x) \to V(x)$.
\\
\\ Man sieht also, dass $P(x)$ sowohl das eine als auch das andere impliziert. Die \"{A}quivalenz der beiden S\"{a}tze lie\ss{}e sich zeigen, wenn man beweisen k\"{o}nnte, dass aus der einen Konklusion die jeweils andere folgt.
\\
\\ Beginnen wir damit zu beweisen, dass aus $V(x)$ die andere Konklusion folgt. Wenn $V(x)$, dann ist der Graph entweder mit h\"{o}chstens drei oder mit genau vier Farben f\"{a}rbbar. Wenn h\"{o}chstens drei Farben gen\"{u}gen, dann ist $\neg N(x)$ erf\"{u}llt (der Graph ben\"{o}tigt keineswegs mindestens vier Farben). Wenn aber die F\"{a}rbung des Graphen des Graphen vier Farben erfordert, dann muss er eine der \"{u}brigen Eigenschaften erf\"{u}llen: $\neg Z$, $\neg K$, $\neg B$ oder $\neg L$.
\\
\\ Daraus, dass genau vier Farben ben\"{o}tigt werden, l\"{a}sst sich nicht $\neg Z$ schlie\ss{}en; der Graph kann ja zusammenh\"{a}ngend sein. Der Schluss auf $\neg L$ ist ebenfalls unzul\"{a}ssig, denn es gibt Graphen, die vier Farben erfordern und einen Ring der Gr\"{o}\ss{}e f\"{u}nf oder h\"{o}her enthalten. Wenn man diese \"{U}berlegungen fortsetzt, wird man darauf kommen, dass eigentlich keine der vier Eigenschaften erf\"{u}llt sein muss. Aber: Es k\"{o}nnte sein, dass jeder Graph, der genau vier Farben erfordert, entweder kubisch ist oder, wenn er nicht kubisch ist, Br\"{u}cken enth\"{a}lt. Wenn dem wirklich so ist, dann ist das Snark-Theorem tats\"{a}chlich eine Schlussfolgerung aus dem Vier-Farben-Satz.
\\
\\ Umgekehrt ist klar, dass zum Beispiel aus $\neg Z(x)$ allein nicht $V(x)$ folgt. Es kann ja ein Graph auch nicht-zusammenh\"{a}ngend sein und dennoch mehr als vier Farben ben\"{o}tigen. Wir m\"{u}ssen aber ber\"{u}cksichtigen, dass der Graph ja auch die Eigenschaft $P$ erf\"{u}llt. Beginnen wir bei den leichteren F\"{a}llen: Wenn $P(x) \wedge \neg K(x)$, dann ist klar, dass $V(x)$, denn ein nicht-kubischer Graph, der keine Knoten enth\"{a}lt, die mindestens drei Nachbarknoten haben, wird sicher nie mehr als vier Farben ben\"{o}tigen. So m\"{u}sste man den Rest durchanalysieren. Ich finde allerdings, dass sich diese Analyse sehr schwierig gestaltet. Man bedenke zum Beispiel: Wenn $P(x) \wedge \neg Z(x)$, dann hei\ss{}t das nur, dass es sich um einen nicht-zusammenh\"{a}ngenden, planaren Graphen handelt. Da dies keine Aussage \"{u}ber die Beschaffenheit der einzelnen Komponenten beinhaltet, bedeutet dies praktisch $P(x) \wedge \neg Z(x) \to V(x) \leftrightarrow P(x) \to V(x)$. Aus $P(x) \wedge \neg Z(x)$ k\"{o}nnen wir also nur dann schlie\ss{}en, dass $V(x)$, wenn wir eh schon wissen, dass $P(x) \to V(x)$ - was wir aber herleiten wollen! Es k\"{o}nnte aber auch sein, dass es Beziehungen zwischen den f\"{u}nf Eigenschaften der Snarks gibt, so dass etwa aus $P(x) \wedge \neg Z(x)$ auch andere Eigenschaften des Graphen folgen - und dann das Ganze logisch wird. Wir haben ja auch im ersten Teil des Beweises von solchen Interdependenzen Gebrauch gemacht.
\\
\\ Ich lade jeden herzlich ein, gemeinsam mit mir weiter zu knobeln - aber vielleicht findet sich ja irgendwo auch der Original-Beweis der \"{A}quivalenz der beiden Theoreme.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
