This is a homework help, it ask us to find the number of spanning trees in this graph.
I can use "matrix tree theorem" to solve it, but that means I need to compute the determinant of a $ 15\times 15$ matrix, which seems an horror to me.
Is there an easier way to compute?
The graph has 16 vertices, so any spanning tree will have 15 edges. The graph starts with 20 edges, so we need to remove 5. We have to break each of the four 5-cycles, so by the pigeonhole principle we will take a single edge from three of the 5-cycles and two edges from one of them.
We also have to break the 4-cycle in the middle. If we remove an edge shared by a 5-cycle and the 4-cycle, we must remove another edge from that 5-cycle, otherwise we end up with an interior 7-cycle. Thus in the 5-cycle that we remove two edges from, one of them must be the edge shared with the 4-cycle.
There are four shared edges to choose from. Once we pick that, there are four other edges in that 5-cycle to remove. Once we do that, each of the three remaining 5-cycles has 5 choices for us to delete one edge from.
Thus in total we have $4\cdot 4 \cdot 5^3 = 2000$ spanning trees.