Bob has recently learned algorithms on finding spanning trees and wanted to give you a quiz.G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected. Given an arbitrary undirected simple graph , a spanning tree removal is defined as: retrieve one spanning tree of the graph, and remove all the edges selected by the spanning tree from the original graph, obtaining a new graph.Bob found "spanning tree removal'' so fun that he wanted to do it over and over again. In particular, he began with a complete graph, i.e., a graph with every pair of distinct vertices connected by a unique edge. Your goal, is to smartly choose spanning trees to remove so that you can repeat as many times as possible until there is no longer a spanning tree in the graph.
Bob has recently learned algorithms on finding spanning trees and wanted to give you a quiz. To recap, a spanning tree is a subset of graph {G} G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected. Given an arbitrary undirected simple graph (without multiple edges and loops), a spanning tree removal is defined as: retrieve one spanning tree of the graph, and remove all the edges selected by the spanning tree from the original graph, obtaining a new graph. Bob found "spanning tree removal'' so fun that he wanted to do it over and over again. In particular, he began with a complete graph, i.e., a graph with every pair of distinct vertices connected by a unique edge. Your goal, is to smartly choose spanning trees to remove so that you can repeat as many times as possible until there is no longer a spanning tree in the graph.
