Is it true that the heaviest edge in a directed graph can not be in the MST of that graph?

I don't think it is true because we might end up with a heaviest edge that is not part of a cycle.

Can anyone confirm?

  • 1
    $\begingroup$ Let $G$ be a graph with a bridge. $\endgroup$ – Pål GD May 9 '13 at 15:24

No, it is not true. Consider a graph with 2 vertices and an edge between them. This is the heaviest edge, and it will be in the minimum spanning tree of $G$.

| cite | improve this answer | |
  • 2
    $\begingroup$ And this is not degenerate example, a leaf node with the heaviest edge... $\endgroup$ – Aryabhata May 9 '13 at 4:03
  • $\begingroup$ Yeah, consider any pendant vertex. $\endgroup$ – Juho May 9 '13 at 4:05
  • 3
    $\begingroup$ Or any edge in a tree. $\endgroup$ – Luke Mathieson May 9 '13 at 4:06
  • 6
    $\begingroup$ More precisely: the heaviest edge is not chosen iff it is on a cycle. $\endgroup$ – Hendrik Jan May 9 '13 at 7:33
  • 1
    $\begingroup$ Every bridge is in every MST. $\endgroup$ – Pål GD May 9 '13 at 15:23

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.