% 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  (again)}
\date{}
\begin{document}
\makeatother
\maketitle



{ \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.23}{%
\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.23}{%
\includegraphics{KnightExchange}%
}
\caption{Knight's positions, before and after.}%
\label{FigureModel}%
\end{center}%
\end{figure}
}

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip

\bigskip


\bigskip

\bigskip

\bigskip


\bigskip

\bigskip

\bigskip



\bigskip

\bigskip

\bigskip


\bigskip

\bigskip

\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.6 }{%
\includegraphics{Eulerian}%
}
\caption{Graphs that may or may not have Eulerian cycles.}%
\label{FigureModel}%
\end{center}%
\end{figure}
}

 \question{Prove that the sum of the degrees of the vertices of any finite graph is even. }

 \bigskip
  
 \question{Show that if n people attend a party and some shake hands with others (but not with them-selves), then at the end, there are at least two people who have shaken hands with the same number of people.}   
\end{document}  