2
$\begingroup$

Let $e$ be an edge of minimum weight in the connected weighted graph $G$. Every minimum spanning tree of $G$ contains $e$.

I have been told that this is not true. But I also know this property : Must a minimum weight spanning tree for a graph contain the least weight edge of every vertex of the graph?

Is it not true because that $e$ is not necessary the only minimum weight edge?

$\endgroup$

1 Answer 1

3
$\begingroup$

If $G$ contains a cycle of edges each of the same minimum weight, then it is not possible for $G$ to have a spanning tree without omitting at least one of those edges.

Otherwise the answer is yes: Let $T$ be a spanning tree of $G$ NOT containing $e$. Then $T+e$ contains one cycle. By assumption, there is an edge in the cycle of non-minimum weight. Remove that edge, and we have a new spanning tree $T'$ of lower weight.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .