Question

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

Short answer

The possible spanning tress are 16.

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 8 and an 9 edges.

The spanning tree will then contain 8 vertices and 7 edges.

Since a tree cannot contain any simple circuits and since there are two squares.The spanning tree can be draw by removing one edge. There are 16 spanning trees.And the some possibilities are

This is the required result.