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 contain any single circuit. And a tree with n vertices has n-1 edges.

Here graph contains 5 vertices and 6 edges.

The spanning tree contains 5 vertices and 4 edges. Thus2 edges will be removed from the graph

Remove the extra edges.

Since a tree cannot contain any single circuit and there are two tangents present in the graph (abd, bce).then suffices to remove one edge from either triangle.

The tree will be as

This is the required result.