\documentclass[12pt]{article}
%\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amsfonts,graphicx,url}

\def\Var{\operatorname{Var}}

\begin{document}

\title{General Mathematics and ACM II}
\author{Midterm Exam}
\date{March 10, 2011}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}


% \vspace*{\fill}

% \newpage

\begin{enumerate}

\item In a finite graph, define the distance $d(u,v)$ between
two vertices $u$ and $v$ as the length of the shortest path between
$u$ and $v$.  Show that $d$ satisfies the ``triangle inequality''
\[
  d(u,v) + d(v,w) \geq d(u,w)
\]
for all vertices $u$, $v$, and $w$.
\hfill (5)
%\newpage
\item
\begin{enumerate}
\item Show that every simple graph with at least two vertices has two
vertices of same valency.

(Recall that a simple graph is a graph without multiple edges between
pairs of vertices.)

\item Give an example that this statement is false if you allow
multiple edges.
\end{enumerate}
\hfill (5+5)
%\newpage
\item Let $G$ be a finite connected planar graph with $V$ its set of
vertices, $E$ its set of edges, and $F$ its set of faces.
\begin{enumerate}
\item Show that $2 \, \lvert E \rvert \geq 3 \, \lvert F \rvert$.
\item Show that $\lvert E \rvert \leq 3 \, \lvert V \rvert - 6$.
\item Conclude that every planar graph with less than $12$ vertices
must have at least one vertex of valency less than $5$.
\end{enumerate}
\hfill (5+5+5)

%\newpage

\item Show that a quadrilateral (a polygon with four edges) is a
trapezoid (a quadrilateral with two parallel edges) if and only if the
length of the line segment joining the midpoints of a pair of opposite
edges is equal to half the sum of the lengths of the other two edges.
\hfill (10)
%\newpage
\item Describe the symmetry group for each of the following ornaments.
\begin{center}
\includegraphics[width=10cm]{iroquois}

\tiny Iroquois and Ojibwa border designs.  From
\url{http://www.oswego.edu/~baloglou/103/crystal.html}
\end{center}
\hfill (10)
%\newpage
\item Recall that the finite cyclic group of order $n$ is
\begin{align*}
  C_n 
  & = \{ \langle a \rangle \colon a^n = e \} \\
  & = \{ e, a, \dots, a^{n-1} \}
\end{align*}
and that the symmetry group of an $n$-gon is the dihedral group
\begin{align*}
  D_n 
  & = \{ \langle a, b \rangle \colon a^n = e, b^2 = e, ab=ba^{-1} \} \\
  & = \{ e, a, \dots, a^{n-1}, b, ba, \dots, ba^{n-1} \} \,.
\end{align*}
Show that any finite subgroup of the motions of the plane
(length-preserving transformations of the plane) is isomorphic to
either $C_n$ or $D_n$ for some $n\geq 1$.

\emph{Note:} This is a typical classification problem where you have
to sift through all possibilities.  Do not expect a short answer.
Full credit will be given if the delineation of the problem is
reasonably complete.  Extra credit for a complete solution.
\hfill (10)
% \newpage
% \null
% \newpage
% \null
% \newpage
\end{enumerate}


\end{document}
