        \problemdata       % Takes 5 *mandatory* arguments
        {min-spanning-tree}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS5-2} % Usage (list ones you are aware of).
        {radhika, fall 01}        % Last revision info (author, date).


\begin{problem}
A \emph{minimum spanning tree} in a connected weighted graph
$G$ is a spanning tree in $G$ with the property that no other spanning
tree in $G$ has a lower total weight. Show that an edge with smallest
weight in a connected weighted graph must be part of any minimum
spanning tree. Assume that the smallest weight edge is unique.

%% Show that any minimum spanning tree must contain an edge with the
%% smallest weight.

\solution{Suppose that an edge $e$ with smallest weight is not
included in some minimal spanning tree; in other words, suppose that
the minimum spanning tree $T$ contains only edges with weights larger
than that of $e$. If we add $e$ to $T$, (thereby completing the unique
path that already exists between the endpoints of $e$) then we will
obtain a graph with exactly one simple circuit, which contains $e$. We
can then delete some other edge in the circuit, without disconnecting
any of the vertices in that circuit. This results in a spanning tree
with weight strictly less than that of $T$ (since all the other edges
have larger weight than $e$ has). This is a contradiction to the fact
that $T$ is a minimum spanning tree. Therefore, an edge with smallest
weight must be included in $T$.}



\end{problem}