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



Your Answer

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

Browse other questions tagged or ask your own question.