Trying to create an algo that creates a spanning tree with least number of edges removed from a unweighed graph

Question

I am trying to create an algo that will get a spanning tree with root node such that, the spanning tree will have least number of edges removed from Original Graph G.

Thanks in advance

Answer 1

For any connected graph, the spanning tree always contains n-1 edges where n is the number of nodes in the graph. So you will have to remove all the remaining edges. (If I have understood your question correctly)

Even for disconnected graphs, the number of edges in a spanning tree is defined by the number of components and number of nodes in each component.