Can I say that if I add e to T and a cycle is formed and if there exists an edge different from e with weight less than e then e cannot be part of any MST? If not then how can I design such an algo?
2026-03-26 06:31:46.1774506706
Given undirected graph G and a MST T of G. Is it possible to design an O(V+E) algorithm to decide if some edge e is contained in a MST of G or not.
28 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Just an answer to your first question: No, you can't say that.
Take a look at this tree: Vertex set: $A,B,C$. Edges: $AB$ with weight $w(AB)=1$ and $BC$ with $w(BC)=3$.
Now add $e=AC$, $w(AC)=2$. Now a cycle is formed and there exists an edge different from $e$ with weight less than $e$. But $e$ is part of the $MST$.