Question

In Exercises 2–6 find a spanning tree for the graph shown byremoving edges in simple circuits.

Short answer

For the result follow the steps.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and that does not contains any single circuit. And a tree with n vertices has n-1 edges.

Here graph contains 10 vertices and 16edges.

The spanning tree contains 10 vertices and 6 edges. Thus10edges will be remove from the graph.

Remove the extra edges.

Since a tree cannot contains any single circuit and there are 10 tangents present in the graph. Then suffices to remove one edge from either triangle. Thus removing the edges (a,h),(a,i),(b,j),(b,i),(c,j),(d,j),(e,j),(f,i),(h,i),(I,j).

Now. The spanning tree will be as

This is the required result.