Question

How many non-isomorphic spanning trees does each ofthese simple graphs have?

a) \({{\bf{K}}_{\bf{3}}}\) b) \({{\bf{K}}_{\bf{4}}}\)c) \({{\bf{K}}_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 does not contain any single circuit. And a tree with n vertices has n-1 edges.

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

The graph with vertices 3 and 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 drawn by removing one edge.

Since one hasa choice of deleting one of the 3 sides of the triangle then three possibilities. The three spanning trees are isomorphic and there is only one non-isomorphic spanning tree

And non-isomorphic is

Sketch non isomorphic 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 drawn by removing one edge.Total possibilities of spanning trees are 16.

There are 14 isomorphic trees.And some spanning trees are

And 2 non-isomorphic trees are

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

This is a graph of 5 vertices and 10 edges.

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

Since a tree cannot contain any simple circuits and similarly by par (b) . The spanning tree can be draw by removing one edge. And the possibilities are 3 non-isomorphicspanning trees are

This is the required result.