Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Graphs and Hashing -Q11

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

How many spanning trees are possible for the graph given below ?

reshown Aug 6, 2020

+1 vote

edge b-g must be included

from both left and right components  out of 5 ,3 edges must be selected  which is possible in C(5,3) =10 ways .

now from left portion  out of these 10 combinations 2 combinations (ab, bc,ac  and   cd,db,cb ) must be excluded as they form a cycle and also do not  cover  remaiining vertex  so total 8 choices are possible.

Similarly from right portion  out of  10 combinations 2 combinations (ef ,fg ,eg   and gh hf gf )   must be excluded as they form a cycle and also do not  cover  remaiining vertex  so again total 8 choices are possible.

so by product rule 8x8 =64 choices are possible
answered Aug 8, 2020 by (18,750 points)
selected Aug 10, 2020
+1 vote

The edge bg has to be in the MST

This problem reduces to multiplying subproblem A and B

subproblem A is identical to B

so it is A^2

Subproblem A:

Number of Spanning tree of abcd subgraph

Using Kirchoff's Matrix tree theorem,

make adjacency matrix out of this

replace diagonal by degree of vertices

and non diagonal elements just put their additive inversive in their place.

now find Minor of any element.

it is given by formula

When you solve it you will get this matrix

Now A= 8

A^2 is 8*8 = 64

Reference