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?


1 Answer 1


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.


You must log in to answer this question.

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