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 21edges.

The spanning tree contains 12 vertices and 11 edges. Thus 10 edges 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,d),(a,e),(a,h),(b,g),(c,j),(e,i),(f,g),(h,l),(I,j),(k,l).

Now. The spanning tree will be as

This is the required result.