How many spanning tree does below graph contains?
I tried to calculate by using edge deletion / contraction approach and I am getting 48:
I tried to calculate it by Kirchoffs method as a determinant of Laplacian matrix:
$$ \left(\begin{matrix}2&0&0&0&0&0&0&0\\0&3&0&0&0&0&0&0\\0&0&3&0&0&0&0&0\\0&0&0&2&0&0&0&0\\0&0&0&0&2&0&0&0\\0&0&0&0&0&3&0&0\\0&0&0&0&0&0&3&0\\0&0&0&0&0&0&0&2\end{matrix}\right) - \left(\begin{matrix}0&1&0&0&1&0&0&0\\1&0&1&0&0&1&0&0\\0&1&0&1&0&0&1&0\\0&0&1&0&0&0&0&1\\1&0&0&0&0&1&0&0\\0&1&0&0&1&0&1&0\\0&0&1&0&0&1&0&1\\0&0&0&1&0&0&1&0\end{matrix}\right) = \left(\begin{matrix}2&-1&0&0&-1&0&0&0\\-1&3&-1&0&0&-1&0&0\\0&-1&3&-1&0&0&-1&0\\0&0&-1&2&0&0&0&-1\\-1&0&0&0&2&-1&0&0\\0&-1&0&0&-1&3&-1&0\\0&0&-1&0&0&-1&3&-1\\0&0&0&-1&0&0&-1&2\end{matrix}\right) $$
I tried to calculate determinant of first co factor, which is Laplacian matrix using wolfram alpha, and it was giving answer 116.
So, I was guessing which is correct answer and where did I make mistake?
PS: I dont have enough reputation to add images inline.
If you delete BF and CG then you need to delete one of the remaining $8$ edges.
If you delete BF but not CG then you need to delete one of the $5$ edges of the LH cycle and one of the $3$ edges of the RH cycle. Similarly for deleting CF but not BF.
If you delete neither BF nor CG then you need to delete one of the $3$ edges for each of the LH and RH cycles and one of BC and FG.
$8+2\times 3\times5+ 3\times3\times2 =56 .$