\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Discussion 4 -- {\it Euleriana}}
\centerline{\it April 8, 2005}
\bigskip
\noindent
{\it Background}
\bigskip
Last time we introduced a number of concepts and terms dealing with
simple and general {\it graphs}.  Here is an additional one.  A
{\it trail} in a graph is a walk with distinct edges.  (You can
visit the same {\it vertex} several times, though.  That's what makes
a trail different from a path.)  Today, we will use this to study
what are called {\it Euler trails} and {\it Euler circuits}.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A) (a ``warm-up'') Recall that the {\it degree} of a vertex
$v$ in a graph $G = (V,E)$ is the number of edges with $v$ as one
endpoint.  What happens if you add up the degrees of all the vertices
in a (simple or general) graph?  Try some examples.
What is always true about the sum?  Prove your claim.
\bigskip
\noindent
The beginnings of graph theory can be traced back to an 
article published by the Swiss mathematician Leonhard Euler
in 1736.  In this article, Euler considered the so-called 
``Bridges of K\"onigsberg'' problem.  The city of K\"onigsberg
(in what is now Poland) was located on two islands and two banks
of a river with bridges in the arrangement given in the diagram on the 
left below:
\vglue 2.0truein
\noindent
The question was:  Is it possible to take a walk through the city 
so that you cross each bridge {\it exactly once}?  Euler's first
innovation was replacing the actual map of the city by an 
equivalent graph, shown in the diagram on the right above.
The vertices $V$ correspond to the different ``land masses'' (the two
islands and the two banks of the river) and the edges represent the
bridges.  
\bigskip
\noindent
B)  By considering the K\"onigsberg graph, Euler found that there is 
{\it no way} to take a walk through the city crossing each bridge exactly 
once.  Why not?  (Explain what goes wrong.)
\bigskip
\noindent
C)  Now, let's ask the same question for an arbitrary connected simple 
graph:  {\it Under what conditions should it be possible to find a trail
that uses each edge in the graph exactly once?}  Thinking as in C, formulate 
a necessary condition.  What must happen at each vertex in a graph if you 
can find a path that uses each edge exactly once?  What happens if 
the trail starts and ends at different points?
\bigskip
\noindent
D)  If you have the right necessary conditions in part C, then 
they also turn out to be sufficient.  Can you prove this?  
You can {\it either}
\item{$\bullet$} try to develop your own proof by saying how to construct
an Euler trail if your conditions are satisfied, or
\item{$\bullet$}  look at Theorems 11.2.2 and 11.2.3
in the text, Read those and write up the 
arguments in your own words, filling in any details that are
not clear to you, and illustrating the arguments with appropriate
diagrams.  
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due in class Wednesday, April 13. 



\bye