Spanning tree of a graph is a subgraph of it which forms a tree and contains (or spans) all the vertices of the graph.
So if the given graph GG has nn vertices, we’re looking for a subgraph of GG which
- has nn vertices
- has n−1n−1 edges
- is connected
Note: The graph itself must be connected in order to obtain its spanning tree.
So if the graph is connected, we just need to delete some of its edges so that there is no cycle and it remains connected.
In these excercises, your aim is to reduce the number of edges to n−1n−1 while keeping the graph connected.
On solving the problems, you will realize that spanning tree of a graph isn’t unique