# Can the heaviest edge ever be in an MST?

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?

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

## 1 Answer

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

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