\documentclass[12pt]{article}
\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{graphicx}
\pagestyle{fancy}
\lhead{MATH 581}
\chead{Practice Exam \#2 Solutions}
\rhead{}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{Febriary 24, 2009}
\begin{document}
\begin{enumerate}
\item {\bf (20 points)} {\em For each of the following graphs $G$,
determine the coloring number $\chi(G)$, connectivity $\kappa(G)$,
clique number $\omega(G)$, whether it has an Eulerian tour, and
whether it has a perfect matching.}
\begin{enumerate}
\item \includegraphics{practice-exam-2-graph-1.ps}
This graph is a tree, which we know to be bipartite, so
$\chi(G)=2$, and which is disconnected by the removal of any
non-leaf vertex, so $\kappa(G)=1$. Since it has no $K_3$ subgraphs
(in fact, no cycle subgraphs of any kind), $\omega(G)=2$. It
clearly has no Eulerian tour, as it has several vertices of odd
degree, and has no perfect matching, as it has an odd number of
vertices.
\item \includegraphics{practice-exam-2-graph-2.ps}
This graph has a $K_5$ subgraph, which demonstrates that
$\omega(G)=5$ and that $\chi(G)\geq 5$. Oen can easily 5-color
this graph, so $\chi(G)$ is actually equal to $5$. Removal of the
two shared vertices will disconnect the graph, so
$\kappa(G)=2$. The two shared vertices have degree $7$, so this
graph has no Eulerian tour. It has a perfect matching, whcih could
be demonstrated by pairing each of the shared vertices with one
vertex from each of the two different cliques, and pairing the two
remaining vertices in each clique.
\item \includegraphics{practice-exam-2-graph-3.ps}
This graph is the complete bipartite graph $K_{3,3}$. Since it is
bipartite, $\chi(G)=\omega(G)=2$. It will be connected as long as
there is at least one vertex in each part, so one needs to remove
3 vertices to disconnect it; thus $\kappa(G)=3$. It has no
Eulerian tour, since every vertex has odd degree. It has several
easily-discovered perfect matchings.
\item \includegraphics{practice-exam-2-graph-4.ps}
This graph has a clique of size 4, so $\omega(G)=4$, and since it
is $4$-colorable, $\chi(G)=4$. Removal of two vertices can
disconnect either of the points outside the $K_4$, so
$\kappa(G)=2$. It has a perfect matching easily determined by
choosing partners for the two vertices outside the $K_4$. It has
an Eulerian tour, since every vertex has even degree.
\end{enumerate}
\item {\bf (40 points)} {\em For each of the following statements,
either prove it (if true) or give a counterexample (if false).}
\begin{enumerate}
\item {\em If $G$ is a simple graph on $2n$ vertices, and $G$ is
$n$-connected, then $G$ has a perfect matching.}
This follows quite easily from Tutte's theorem: for a subset $S$
of $V(G)$, we can see that $G-S$ has at most $|S|$ odd components
no matter how large $S$ is. If $|S|=0$, then $G-S=G$ which is a
connected graph with an even number of vertices and has zero odd
components. If $0<|S|