number of min MSTs

Question

Comments

I’m getting 48 as answer. in graph we have 10 vertices so we need 9 edges to form a MST.

Edges AF,EG and DH have to be chosen because of minimum weight and they don’t form a cycle with each other.3 edges done.now we need to choose 6 more edges.now choosing 6 edges can be done in 3 ways.

1) From cycle A-B-C-D-E i choose 4 edges and from the cycle F-G-H-J-I i choose 2 edges.this can be done in $\left(\begin{array}{l}5 \\ 4\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)$.

2) from cycle A-B-C-D-E i choose 2 edges and from the cycle F-G-H-J-I i choose 4 edges.this can be done in $\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}5 \\ 4\end{array}\right)$.

3) from cycle A-B-C-D-E i choose 3 edges and from the cycle F-G-H-J-I i choose 3 edges.
1) first select edges AE and GH. and then from the cycle A-B-C-D-E i can select any 2 edges out of AB,BC,CD and similarly you can select any 2 edges out of FI,IJ and JH from the cycle F-G-H-J-I.
OR
2) select edges ED and GF and then you can add edges such that you don’t create a cycle.

finally we have  $\left(\begin{array}{l}5 \\ 4\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)$$+$$\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}5 \\ 4\end{array}\right)$$+$$\left(\begin{array}{l}3 \\ 2\end{array}\right)\left(\begin{array}{l}3 \\ 2\end{array}\right)*2$ $=$ $48$

---

From cycle A-B-C-D-E i choose 4 edges AE-AB-BC-CD

and from the cycle F-G-H-J-I i choose 2 edges   HG-FG

AE-AB-BC-CD-DH-HG-GE is a cycle and hence not MST right

---

I never told that I'll choose 2 edges HG and FG if i selected 4 edges AE-AB-BC-CD from the cycle A-B-C-D-E.

what i meant was if we select 4 edges from the cycle A-B-C-D-E, then from the cycle F-G-H-J-I there are 3 ways to select 2 edges.

Answer 1

AF-EG-DH since they have least weight

one of AE,ED,GF,HG

from AB,BC,CD,FI,IJ,HJ any 5

(4C1)*(6C5)=24