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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.