\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSU690}{Algorithms and Data}{Fall 2006}{17 October 2006}{11}

\begin{center}
\Large{\bf Review 4 (Tuesday, October 17)}
\end{center}

For each of the following three statements, decide whether the
statement is true.  If it is true, then provide a proof; otherwise,
give a counterexample.

{\bf 1.} Let $G$ be an undirected connected graph with nonnegative
weights on edges.  Let $T$ be a minimum spanning tree of $G$.  Then,
for any vertex $u$ and $v$, the unique path between $u$ and $v$ in $T$
is the shortest path between $u$ and $v$ in $G$.

\vfill

{\bf 2.} Let $G$ be an undirected connected graph with weights on
edges, and let $T$ be an MST of $G$.  Suppose we add $W$ to the weight
of every edge.  Then, $T$ remains an MST of the graph with the new
weights.

\vfill

\newpage

{\bf 3.} Let $G$ be an undirected connected graph with weight $w(e)$
on every edge $e$.  Suppose $e^*$ is a lightest edge in $G$; that is,
$w(e^*) \le w(e)$ for all edges $e$.  Then, there is an MST $T$ of $G$
that contains $e^*$.

\end{document}