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 12 vertices and 27 edges.

The spanning tree contains 12 vertices and 11 edges. Thus16 edges will be remove from the graph.

Remove the extra edges.

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

Now. The spanning tree will be as

This is the required result.