% This file was converted to LaTeX by Writer2LaTeX ver. 0.4
% see http://www.hj-gym.dk/~hj/writer2latex for more info
\documentclass[10pt,twoside]{article}
\usepackage[ascii]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsthm,amsmath,amssymb,amsfonts,textcomp}
\usepackage{color}
\usepackage{calc}
\usepackage{hyperref}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper} 

\newtheorem{theorem}{Theorem}
\theoremstyle{definition} 
\newtheorem{question}{Problem}

% Check if we are compiling under latex or pdflatex, and include the
% appropriate graphics package
\ifx\pdftexversion\undefined
 \usepackage[dvips]{graphicx}
\else
 \usepackage{graphicx}
\fi


\title{Graphs}
\date{}
\begin{document}
\makeatother
\maketitle




 \question{How many times can three people shake hands if each person shakes hands with each other person exactly once? Same question for four people? Five people? Six? Ten?} 

\bigskip
 
\bigskip

\bigskip

\bigskip

\bigskip

\bigskip


\bigskip

\bigskip


\bigskip

\bigskip

\bigskip





 \question{In a certain kingdom, the are 8 cities, and three roads lead out of each city. How many roads are  there  in  the  kingdom? What if there were 12 cities, and three roads leading out of each? Now suppose there are 20 cities and four roads out of each? Lastly, what if there are three cities with three roads leading out of each?} 
 
 \bigskip
 
\bigskip

\bigskip

\bigskip


\bigskip

\bigskip

\bigskip


\bigskip

\bigskip

\bigskip

\bigskip







 \question{Can a kingdom in which 3 roads lead out of each city have exactly five roads? Can it have exactly six roads? Ten? Fifteen? } 

\vspace{1.3in}
{
 \question[\emph{Think about using graphs}]{A chessboard has the form of a cross, created from a $4 \times 4$ chessboard by deleting the corner squares. Can a knight travel around this chessboard, using the usual knight's move, passing through each square exactly once, and end up on the same square it starts on?} 
 


\begin{figure}[h]%
\begin{center}%
\scalebox{0.27}{%
\includegraphics{KnightsTour}%
}
\caption{Knight's tour.}%
\label{FigureModel}%
\end{center}%
\end{figure}

}
{
 
 \question[\emph{Again, think about using graphs}]{{Four knights are positioned on a $3 \times 3$ chessboard as shown on the first chessboard below. Can they move to the positions shown on the second chessboard? } 


\begin{figure}[h]%
\begin{center}%
\scalebox{0.36}{%
\includegraphics{KnightExchange}%
}
\caption{Knight's positions, before and after.}%
\label{FigureModel}%
\end{center}%
\end{figure}
}

\bigskip

 \question{Is it possible in any of the following graphs to start at one vertex and travel across each edge exactly once arriving at the vertex you started from? Such a trip is called an Eulerian cycle. Is there a  characteristic that distinguishes the graphs that have Eulerian cycles from those that don't?}  
 
 \bigskip
 
\begin{figure}[h]%
\begin{center}%
\scalebox{0.65}{%
\includegraphics{Eulerian}%
}
\caption{Graphs that may or may not have Eulerian cycles.}%
\label{FigureModel}%
\end{center}%
\end{figure}
}
 
\end{document}  