\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb,amsmath}
\usepackage[pdftex]{graphicx}
\topmargin = 0.1in \textwidth=5.7in \textheight=8.6in
\oddsidemargin = 0.2in \evensidemargin = 0.2in
\begin{document}
\begin{center}
\large
COMPUTER SCIENCE 20, SPRING 2012 \\
DISCRETE MATHEMATICS FOR COMPUTER SCIENCE\\
\medskip
Class \#18 (Simple Graphs)
\end{center}
\paragraph{Homework, due in hard copy Wednesday 3/21/2012 at 10:10am}
\paragraph{Please write your TF's name on your homework, and list the names of any students with whom you collaborated.}
\begin{enumerate}
\item Answer the following questions about the Handshaking Lemma.\footnote{Credit: Albert R. Meyer, MIT 6.042}
\begin{enumerate}
\item Prove that in every graph, there are an even number of vertices of
odd degree. \emph{Hint: Use the Handshaking Lemma.}
\item \label{oddnumeven} Conclude that at a party where some people shake
hands, the number of people who shake hands an odd number of times is an
even number.
\item Call a sequence of two or more different people at the party a
\emph{handshake sequence} if, except for the last person, each person in
the sequence has shaken hands with the next person in the sequence.
Suppose George was at the party and has shaken hands with an odd number of
people. Explain why, starting with George, there must be a handshake
sequence ending with a different person who has shaken an odd number of
hands.
\emph{Hint: Look at the people at the ends of handshake sequences that
start with George.}
\end{enumerate}
\end{enumerate}
\end{document}