Number of spanning trees of graph on picture

Question

I have to find number of spanning trees of the given graph. I don't think that matrix theorem for trees is optimal here because I would need to calculate determinant of matrix $9$x$9$. Then, recursive formula for spanning trees is also a lot of work because we have so many edges on cycles here. I would like to know if there is some optimal solution, because here we can see graph $K_5$ that is connected with $K_3$ and two more edges. Because we know number of spanning trees of complete graph is $n^{n-2}$ where $n$ is number of vertices, I thought that we can use some trick including this. Any help is appreciated.

Answer 1

Yes, I think you're right. The number of spanning trees of the given graph is $5^3\cdot3^1=475$.

Answer 2

Just to add a little more theory to kabenyuk's correct answer. Any given graph can be decomposed into its maximal 2-connected components. Replacing each 2-connected component with a single vertex always gives a tree graph (I think there is a name for this but I can't think of it right now). One can then show that a spanning tree of the entire graph always consists of this tree graph plus a spanning tree of each 2-connected component. Hence the number of spanning trees of the entire graph is the product of the number of spanning trees of the 2-connected components. This should be explained in most graph theory text books, I read it in Diestel.

In the example given above the two 2-connected components are a $K_5$ and a $K_3$ with $5^3$ and $3$ spanning trees respectively. So this gives $5^3\times 3$ spanning trees for the entire graph.