Question

How many different spanning trees does each of thesesimple graphs have?

a)\({{\bf{K}}_3}\)b)\({{\bf{K}}_{\bf{4}}}\) c) \({{\bf{K}}_{{\bf{2,2}}}}\)d) \({{\bf{C}}_{\bf{5}}}\)

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.

Spanning tree \({{\bf{K}}_{\bf{3}}}\).

The graph with vertices 3 and an 3 edges.

The spanning tree will then contain 3 vertices and 2 edges.

Since a tree cannot contain any simple circuits and since there is a triangle. The spanning tree can be draw by removing one edge. And the three possibilities are

Sketch spanning tree for\({{\bf{K}}_{\bf{4}}}\).

This is a graph of 4 vertices and 6 edges.

The spanning tree will then contain 4 vertices and 3 edges.

Since a tree cannot contain any simple circuits and since there is a square. The spanning tree can be draw by removing one edge.

Use the concept of combination \(C\left( {6,3} \right) = \frac{{{\rm{6!}}}}{{{\rm{3! ) 3!}}}} = 20\).And some spanning trees are

Plot spanning tree\({{\bf{K}}_{{\bf{2,2}}}}\).

This is a graph of 2 vertices M=(a,c) and another set of 2 vertices N=(b,d).All vertices in M are connected to vertex in N.

The spanning tree will then contain 4 vertices and 3 edges.

Since a tree cannot contain any simple circuits and since there is a square. The spanning tree can be draw by removing one edge. And the possibilities are 4 spanning trees.

Plot spanning tree for\({{\bf{C}}_{\bf{5}}}\).

The graph with 5 vertices and an edge between every pair of vertices.

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

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once. The spanning tree can be draw by removing one edge. The possibilities of 5 spanning trees.

This is the required result.