0
$\begingroup$

Given an undirected weighted connected graph. How to determine the edges that appear
in all minimum spanning trees. I know the Kruskal and Prims algorithm to find
a minimum spanning tree. But how does one ensure that a particular edge appears in
all possible minimum spanning trees?

My Thoughts:
If an edge has degree 1, that will be for sure in all minimum spanning trees.
If an edge belongs to a cycle, then that edge will not be in all MST
I am not sure how to proceed from here, or I could use some algorithm to determine it

$\endgroup$
2

0

Your Answer

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

Browse other questions tagged or ask your own question.