2
$\begingroup$

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?

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

1 Answer 1

9
$\begingroup$

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$.

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

Your Answer

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

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