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.
Best Answer
Yes, I think you're right. The number of spanning trees of the given graph is $5^3\cdot3^1=475$.