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

\begin{document}

\title{General Mathematics and Computational Science II}
\author{Midterm Exam}
\date{March 13, 2015}
\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 A bipartite graph with vertex sets $V_1$ and $V_2$ is
\emph{complete} if there is an edge between every vertex in $V_1$ and
every vertex in $V_2$.

\emph{Notation:} The complete bipartite graph with $\lvert V_1
\rvert = n$ and $\lvert V_2 \rvert = m$ is called $K_{n,m}$.
$K_{1,m}$, for any $m \in \mathbb N$, is called a \emph{star}.

\begin{enumerate}
\item What is the number of edges of $K_{n,m}$?

\item Show that if a graph is complete bipartite and is a tree, then
it is a star.

\item Show that $K_{3,3}$ cannot be embedded in the plane.
\end{enumerate}
\hfill(5+5+5)


\item In the following graph, find the shortest closed path that
traverses every edge at least once.

\begin{center}
\includegraphics[width=5cm]{squaregrid.pdf}
\end{center}

Your answer should include
\begin{enumerate}
\item a correct solution;
\item an argument that there is no shorter such path.
\end{enumerate}
\hfill(5+5)


\item Given a circle with center $O$ and a point $P$ outside of it,
suggest a construction using only Euclidean transformations
(translation, reflection, rotation) to find a point $S$ on the circle
where the line segment $PS$ is tangent to the circle.
\hfill(10)
\begin{center}
\includegraphics[width=10cm]{tangent.pdf}
\end{center}


\item Given two lines $\ell_1$ and $\ell_2$, set
$\ell_2'=R_{\ell_1}(\ell_2)$, i.e., $\ell_2'$ is the reflection of
$\ell_2$ about
 $\ell_1$.

Show that
\[
  R_{\ell_2} \, R_{\ell_1} = R_{\ell_1} \, R_{\ell_2'} \,.
\]
\hfill(5)


\item For each of the following, determine whether or not it is a
group.  If it is a group, give a full argument why; if it is not,
state at at least one property that fails.
\begin{enumerate}
\item The set of real $n\times n$ matrices under matrix
multiplication;
\item the orientation-preserving motions of the plane under
composition;
\item the orientation-reversing motions of the plane under
composition.

\end{enumerate}
(A motion or Euclidean transformations of the plane is called orientation-preserving if a
clock-wise traversal of a cycle is mapped onto clock-wise traversal of
its image; it is orientation-reversing otherwise.)  \hfill(4+3+3)


\item Let $R_\alpha$ denote the reflection
about the line $x=\alpha$.  Let $G$ be the (symmetry) group generated
by the unit translation along the $x$-axis and by $R_0$.  Show that
$R_\alpha \in G$ if and only if $2 \alpha \in \mathbb{Z}$.
\hfill (10)
\end{enumerate}


\end{document}
