Given a graph G, if the graph is interconnected, possibly containing a cycle, who do we find a minimum spanning tree at all? Most texts I've seen don't seem to explain the reason at all. Why don't we find a subgraph in the graph possibly containing a cycle whose weight is minimized, possibly by removal of some edges?
2026-04-12 14:09:34.1776002974
reason for finding a spanning tree
32 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
If you want a connected spanning subgraph whose total edge weight is minimized, it will necessarily be a tree. Trees are precisely the minimally connected graphs: graphs that don't contain any edge you can remove and still have a connected graph.
If you don't need the subgraph to be connected, then the total edge weight is minimized by not taking any edges at all...