Chapter 11: Q11E (page 795)
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
Over 22 million students worldwide already upgrade their learning with Vaia!
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.
