\documentclass[11pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}

\def\BOX#1{\fbox{\vbox to #1{\vss\hbox to #1{\hss}}}}
\def\Bigbox{\BOX{0.25in}}
\def\Bigbox{\raisebox{-0.5ex}[0.25in][0pt]{\BOX{0.25in}}}

% =========================================================
\begin{document}

\begin{center}
\LARGE \textbf{CS 173: Discrete Mathematical Structures, Fall
2009}
\\
\textbf{Honors Homework 4}
\\[1ex]
\Large Due by 5pm on 
Wednesday December 9th.
Please give to Margaret 
or push it under the door of Margaret's office (3214 Siebel).

Since this involves a lot of drawing, it might be a pain to do
it in latex and, therefore, handwritten is ok.

\end{center}

\section{Background}

Read the four scanned pages (from the textbook by Norman Biggs)
posted on the web page.   You may also want to remind yourself
(e.g. from the text or lecture notes) what it means for a graph
to be bipartite.

A Latin square of order $n$ is an $n$ by $n$ array whose entries
are taken from a set of $n$ symbols.   Each symbol must occur
exactly once in each row and exactly once in each column.
For example, the following is a latin square of order 5.

\begin{tabular}{lllll}
A & B & C & D & E \\
B & C & A & E & D \\
C & D & E & A & B \\
D & E & B & C & A \\
E & A & D & B & C \\
\end{tabular}


Latin squares are useful for designing a sequence of experiments
that systematically cover a range of conditions without requiring
excessive numbers of trials.

\section{To do}


Do Exercises 1 and 4 from section 17.2.

Also use the edge-coloring method to extend the following latin
rectangle to a 5 by 5 latin square.   Show your completed 5 by 5 
square and also a picture of the bipartite graph coloring (as in
the middle part of figure 17.6).    I found that it was helpful to
draw the graph with the symbols or the columns out of order, so
as to minimize the number of crossing lines.

\begin{tabular}{lllll}
A & B & C & D & E \\
C & D & B & E & A \\
B & C & E & A & D \\
\end{tabular}




\end{document}
