# Each cycle in the graph, the edge with the minimum weight belongs to MST

Let $$G=(V,E)$$ be a weighted undirected connected graph and $$w: E \to \mathbb{R^{+}}$$ a weight function so that there are no two edges that have the same weight, and $$T$$ is an MST of $$G$$ . Then in each cycle in the graph, the edge with the minimum weight belongs to $$T$$.

I either need to prove it in a positive way or give a counterexample.

• Please do not edit your question to remove useful content. That way the answers can help anyone else who has the same problem you were experiencing, and it will allow us to make a stronger site for helping people. See cs.stackexchange.com/help/editing.
– D.W.
Commented Feb 3, 2021 at 19:46

Following is a simple counterexample: Take a complete graph on four vertices: $${u_{1},u_{2},u_{3},u_{4}}$$, with edge weights $$w(u_{1},u_{2}) = 1$$, $$w(u_{2},u_{3}) = 2$$, $$w(u_{1},u_{3}) = 4$$, $$w(u_{1},u_{4}) = 5$$, $$w(u_{2},u_{4}) = 3$$, and $$w(u_{3},u_{4}) = 6$$. Here MST is composed of edges: $$(u_{1},u_{2})$$, $$(u_{2},u_{3})$$, and $$(u_{2},u_{4})$$ with total weight $$6$$. And, no edge of the cycle $$(u_{1},u_{3},u_{4})$$ is part of the MST.