% Math 320 hw5
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in]{geometry}

\usepackage{mathtools, nccmath}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{verbatim}

% hyperref should be (nearly) the last package loaded
\usepackage{hyperref}

\usepackage{xparse}

%This very cool macro comes from
%http://tex.stackexchange.com/questions/209863/how-to-add-mathematical-notation-of-a-set
%
% \set{ stuff ; something }  
% expands to
% { stuff | something }
%
\DeclarePairedDelimiterX{\set}[1]{\{}{\}}{\setargs{#1}}
\NewDocumentCommand{\setargs}{>{\SplitArgument{1}{;}}m}
{\setargsaux#1}
\NewDocumentCommand{\setargsaux}{mm}
{\IfNoValueTF{#2}{#1} {#1\,\delimsize|\,\mathopen{}#2}}%{#1\:;\:#2}
\newtheorem{theorem}{Theorem}

\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/320}

\title{Discrete Mathematics \\
Homework 5
}
\author{Ethan Bolker}
%\date{September 1, 2014}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}


%create (mod n) macro
\newcommand{\mm}[1]{%
\ensuremath{(\text{mod } #1)}}

\begin{document}

\maketitle

\noindent
Due: Last class, December 11.

This homework covers problems about graphs, and some about games.
You can read about graphs in B\&W at
\url{http://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C2U4GT.pdf}.

You can read about games at \url{\coursehome/FergusonGames.pdf}.

If you want to include figures -- for example, sketches of graphs --
you can draw them by hand and scan them, or learn tikz, or if
necessary, turn in hand drawn sketches.

\section*{Exercises}

\begin{enumerate}

\item Prove that in any finite graph the number of vertices of odd
  degree is even.

\textbf{Solution} 

When I add up the degrees of the vertices each edge
will be counted twice, so the sum will be even. If a sum of numbers is
even then there must be an even number of odds.

\item \emph{Dirac's Theorem} says that if in a \emph{simple} graph
  with $n \ge 3$ every vertex has degree at least $n/2$ then the graph
  has a Hamiltonian cycle.

That Dirac is \emph{not} the Nobel Prize winning physicist
P. A. M. Dirac.

A \emph{simple} graph is an undirected graph with no loops and no
multiple edges. 

Show that the converse of Dirac's Theorem is false for graphs with at
least $3$ vertices.

\textbf{Solution} 

This is a little hard to parse. The converse is false because the
existence of a Hamiltonian cycle doesn't force $n/2$ vertices. Any
\emph{cycle} of length five or more provides a counterexample.

\item K\"onigsberg updated

Here is a story that starts with the classic problem and asks some
questions. Answer them.

I didn't make this up. It's very easy to find on the internet, along
with a solution. But the questions are easy, so please don't look up
the answers.

Here's the picture:

\begin{center}
\includegraphics[width= 2in]{konigsbergplus}
\end{center}

The northern bank of the river is occupied by the Schloss, or castle,
of the Blue Prince; the southern by that of the Red Prince. The east
bank is home to the Bishop's Kirche, or church; and on the small
island in the center is a Gasthaus, or inn. 

It is understood that the problems to follow should be taken in order,
and begin with a statement of the original problem: 

It being customary among the townsmen, after some hours in the
Gasthaus, to attempt to walk the bridges, many have returned for more
refreshment claiming success. However, none have been able to repeat
the feat by the light of day. 

The Blue Prince, having analyzed the town's bridge system by
means of graph theory, concludes that the bridges cannot be walked. He
contrives a stealthy plan to build an eighth bridge so that he can
begin in the evening at his Schloss, walk the bridges, and end at the
Gasthaus to brag of his victory. Of course, he wants the Red Prince to
be unable to duplicate the feat from the Red Castle. Where does the
Blue Prince build the eighth bridge? 

The Red Prince, infuriated by his brother's Gordian solution
to the problem, wants to build a ninth bridge, enabling him to begin
at his Schloss, walk the bridges, and end at the Gasthaus to rub dirt
in his brother's face. As an extra bit of revenge, his brother should
then no longer be able to walk the bridges starting at his Schloss and
ending at the Gasthaus as before. Where does the Red Prince build the
ninth bridge? 

The Bishop has watched this furious bridge-building with
dismay. It upsets the town's Weltanschauung and, worse, contributes to
excessive drunkenness. He wants to build a tenth bridge that allows
all the inhabitants to walk the bridges and return to their own
beds. Where does the Bishop build the tenth bridge? 

Two more questions:

\begin{itemize}

\item Most of the German words in this passage are
translated there. One is not. What does ``Weltanschauung'' mean?
Please explain in your own words. Don't just paste in a dictionary
definition.

\item Why does the Red Prince call his brother's solution ``
  Gordian''?

\end{itemize}

\textbf{Solution} 

For the puzzle, see the Variations on the Wikipedia page
\url{http://en.wikipedia.org/wiki/Seven_Bridges_of_K\%C3\%B6nigsberg}.

The web will answer the other two questions too.

\item Generalizing Euler's Theorem

Euler's theorem for planar connected graphs says
\begin{equation*}
        F - E + V = 1
\end{equation*}
%
where $F$ is the number of regions, $E$ the number of edges and $V$ the
number of vertices.

Discover and then prove a generalization for a planar graph with $C$
connected components. Your formula should reduce to Euler's when $C=1$.

\textbf{Solution} 

For a planar graph
\begin{equation*}
        F - E + V - C = 0
\end{equation*}
where $C$ is the number of components. This is pretty easy to
prove. If you use Euler's formula for each component and add the
resulting equations you get $C$ on the right hand side. I just moved
it to the left as $-C$ for extra elegance.

\item Nonplanar graphs

On page 124 of David Richeson's 
\emph{Euler's Gem} (\url{http://www.eulersgem.com/} you can find the
following proof that $K_5$, the complete graph on five points, is not
planar.


\begin{quotation}
Suppose $K_5$ is a planar graph. Then we can draw
$K_5$ in the plane so that no edges cross. $K_5$ has $5$
vertices and $10$ edges. Euler's formula for planar graphs states that
$V-E+F=2$ [counting the outside of the graph as one of the faces], thus
our planar drawing of $K_5$ must have $7$ faces including the
unbounded face (because $2 = 5 - 10 + F$).

Each edge borders two faces, so $2E = pF$, where $p$ is the average number
of sides on all faces. $K_5$ is a complete graph, so it has no
loops or parallel edges. Because there are no loops, there are no
faces bounded by only one edge, and because there are no parallel
edges there are no faces bounded by two edges. Thus the average number
of edges per face is at least three. So, $p \ge 3$ and $2E \ge 3F$. But $F =
7$ and $E = 10$ implies that $20 \ge 21$, which is a
contradiction. It must be that $K_5$ is non planar.

In a similar way we can prove that the complete bipartite graph
$K_{3,3}$ is not planar (give it a try!). The key difference is
that because $K_{3,3}$ is bipartite, a path that begins and ends
at the same vertex must have an even number of edges. So there can be
no three-sided faces either.
\end{quotation}

Your job: complete the proof suggested in the last paragraph.

\textbf{Solution} 

Suppose $K_{3,3}$ is a planar graph. Then we can draw
$K_{3,3}$ in the plane so that no edges cross. $K_{3,3}$ has $6$
vertices and $9$ edges. Euler's formula for planar graphs states that
$V-E+F=2$ [counting the outside of the graph as one of the faces], thus
our planar drawing of $K_{3,3}$ must have $5$ faces including the
unbounded face (because $2 = 6 - 9 + F$).

Each edge borders two faces, so $2E = pF$, where $p$ is the average number
of sides on all faces. $K_{3,3}$ has no
loops or parallel edges. Because there are no loops, there are no
faces bounded by only one edge, and because there are no parallel
edges there are no faces bounded by two edges. Because it is
bipartite, every cycle has even length, so there are no faces bounded
by three edges.
Thus the average number
of edges per face is at least four. So, $p \ge 4$ and $2E \ge 4F$. But $F =
5$ and $E = 9$ implies that $18 \ge 20$, which is a
contradiction. It must be that $K_{3,3}$ is non planar.


\end{enumerate}
\newpage

\verbatiminput{\jobname}

\end{document}




