Question

In Exercises 2–6 find a spanning tree for the graph shown by removing 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 7 vertices and 14 edges.

The spanning tree contains 7 vertices and 6 edges. Thus8 edges will be remove from the graph.

Remove the extra edges.

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

Since all curve edges in the remaining graph still create a circuit.so remove other edges are (a,d),(d,g),(e,g).

Now. Thespanning tree will be as

This is the required result.