Question

In Exercises 8–10 draw all the spanning trees of the given simple graphs.

Short answer

The possible spanning trees are 4.

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.

Spanning tree.

The graph with vertices 6 and an 6 edges.

The spanning tree will then contain 6 vertices and 5 edges.

Since a tree cannot contain any simple circuits and since thereis a square. The spanning tree can be draw by removing one edge. There are 4 spanning trees.

This is the required result.