i will use the same approach as i used here https://gateoverflow.in/262827/self-doubt-spanning-tree#a262893
i have numbered the node.
total edges are 9 .For mst edges will be v-1=5
step 1 : total combination
9c5=126
but this combination contains 3 edges,4edges,5 edges cycle.so subtraction from these must be done.
step 2: finding 3 edges cycle
3 edges cycle are (123,245,235,356)- 4 cycles
now for each cycle 2 edges are remaining so choosing those 2 edges will take 6c2 ways.
total=4*6c2
but if we choose 2 more edges then there may be chances of getting 4 edges cycle.
for example- in cycle 123 if we choose edge 5-3 and 2-5 cycle 1253 is possible,in cycle 235 if we choose 2-4 & 4-5 then 2354 is possible also in same cycle if we choose edge 3-6,5-6 then cycle 2365 is possible.
3 EDGES CYCLE EDGES ADDED 4 EDGES CYCLE FORMED
123 5-3,2-5 1253
245 2-3,3-5 2354
235 5-4,2-4 or 3-6,5-6 OR 1-2,1-3 2354 OR 2365 OR 1253
356 2-5,2-3 2365
so total 6 (4-edges cycle) will be formed so we must remove this 6 cycles
4*6c2-6=54
case 3: finding 4 edges cycle (1253,2453,2563)
choosing the fifth edges will take 5c1 ways but we have to careful that choosing 5th edges can lead us to 5 edges cycle.
4 EDGES CYCLE EDGES ADDED 5 EDGES CYCLE
1253 2-3 231253
2453 2-5 253245
2563 3-5 356325
So 3 5EDGES WILL BE FORMED SO WE MUST REMOVE THESE 3 CYCLES 3*5c1-3=12
case 4:choosing 5 edges cycle(231253,253245,532563,421354,521365,236542)
total 6
final answer:126-(54+12+6)=54