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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 3, 2021 at 19:46

1 Answer 1


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.

  • 1
    $\begingroup$ I'm sure there are pliny others too. $\endgroup$
    – Jasen
    Feb 3, 2021 at 10:52
  • 1
    $\begingroup$ Kudos for the simplest possible example. $\endgroup$
    – vonbrand
    Feb 6, 2021 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.