\magnification=\magstep1
\overfullrule=0pt
\nopagenumbers
\centerline{MONT 106Q -- Mathematical Thinking}
\centerline{Discussion on Graphs and Eulerian Paths}
\centerline{October 28, 2016}
\bigskip
\noindent
{\it Background}
\bigskip
The Bushoong people of Zaire make sand drawings of several kinds illustrating the results on Eulerian 
paths in graphs that we discussed last time.  Today, we will consider
two types extending those on pages 33 to 37 of Ascher's book.
\bigskip
\noindent
{\it Questions}
\bigskip
\noindent
I.  The Bushoong sand figure in Figure 2.2a on page 35 is just one of a whole family
of figures constructed according to a similar pattern.  We will use the following
notation for these.  We will call the design in Figure 2.2a the figure $B_2$ because
the vertices form {\it two} diamonds side by side.  There is a similar figure $B_k$
for each integer $k \ge 1$.  For instance, here are the figures $B_1$ on the left
and $B_3$ on the right:
\bigskip
\bigskip
\bigskip
\noindent
{\it Note:}  $B_1$ has 1 central diamond; $B_3$ has 3 of the central diamonds.
\bigskip
\item{A)}  How many vertices and edges do each of the figures $B_1,B_2,B_3$ have?
\item{B)}  What about the general case?  How do the numbers of vertices and edges 
depend on $k$?  Can you prove your result?  (Hint:  the technique of {\it mathematical induction} is the
quickest way if you have seen that in a course before; if not ask me and I'll tell
you the idea.)
\item{C)}  Explain why {\it all} of the $B_k$ figures have Eulerian paths. 
\bigskip
\noindent
II.  On pages 36 and 37, Ascher discusses the way Bushoong children actually trace out the 
figures shown in Figure 2.2b and c.  These types have Eulerian paths starting at one vertex
of odd degree and ending at the other vertex of odd degree.  Ascher gives what amount
to {\it algorithms} for drawing these figures, expressed as series of drawing commands.
\bigskip
\item{A)} Exactly what is an {\it algorithm}?  Look up a precise definition and explain 
how it relates to what Ascher is saying here.
\item{B)} Draw the figures for $N = 6$, $N = 8$, and $N = 12$ using the general algorithm
at the bottom of page 36.  You will find it easiest to use graph paper for this -- rotate
the paper by 45 degrees so that the grid of the graph paper can be used to draw the lines
in the ul, ur, dl, and dr directions as directed.
\item{C)}  Now look at the modified algorithm at the top of page 37.  How does that
generalize to a general even number $N$ (the given special case is $N = 10$).  
\item{D)}  Following your algorithm from C, draw the figures specified by $N = 6$ and $N = 8$.
\end