\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{25 November 1998}{22}

\begin{center}
\Large{\bf Problem of the Week -- 9}
\end{center}

Let $G$ be a weighted connected undirected graph.  
\begin{Enumerate}
\item[(a)]
Prove that if $T$ and $T'$ are two minimum spanning trees of $G$, then there
exists a sequence $\langle T_0,\ldots,T_k\rangle$, $k\geq 0$, such that: (i)
$T_i$ is a minimum spanning tree of $G$, $0\leq i\leq k$, (ii) $T_0=T$, (iii)
$T_k=T'$, and (iv) $|T_{i+1}\setminus T_i|=1$, $0\leq i<k$ (i.e., $T_i$ and
$T_{i+1}$ differ in exactly one edge).

\item[(b)]
Prove that if $T$ and $T'$ are two minumum spanning trees, then $T$ and $T'$
have the same ``weight distribution'' (i.e., for any weight $w$, both $T$ and
$T'$ contain the same number of edges with weight $w$).
\end{Enumerate}

\end{document}
