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?


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.