Finding number of spanning trees 


I understand how the deletion-contraction recurrence works, but I don't get how they managed to deduce the number of spanning trees for the graphs in the 4th row.
 A: I'll expand on my Comment and relate specifics for counting some of the spanning trees in the fourth row of the diagram above.
A spanning tree must have exactly one fewer edge than there are nodes to be spanned, a result usually proven (by induction) early in any treatment of graphs.  In particular fewer than that many edges cannot gives us a connected graph (and trees are connected, acyclic).
Now if the number of edges is not much more than the number of nodes, we will not have a lot of flexibility in choosing which ones can be removed, especially once edges whose removal would disconnect the graph are discounted.
The last graph in that fourth row is an easy illustration of this.  There are nine nodes and nine edges, so we have to pick some edge to remove to get a spanning tree.  Of the nine edges, there is one that will obviously disconnect the graph if removed, so discount that one.  Therefore we have eight valid choices of edges to remove, hence eight spanning trees in that last graph.
Next to it in the row, on the left, there is a graph with eight nodes and nine edges.  Thus we have to pick two edges to remove (in order to get a spanning tree).  Every cycle in the graph needs to contain at least one of those edges.  We have five choices of edges to remove from the 5-cycle on the left and five to choose from on the right.  Thus we would have 5x5 choices, except that these two 5-cycles share an edge, so if that is removed it doesn't count as removing two edges (only one) and another edge also needs to go.  Check the arithmetic, but there are (5x5 - 1) valid possibilities (spanning trees).
Okay, one more: the rightmost graph in the left half of the fourth row.  It has eight nodes and nine edges, so again we need to remove two of the edges.  This time there's a 3-cycle on the left half and a 5-cycle in the right half, but to make things easy these do not share an edge (though they do share a node).  The valid choices are any pair of edges, one from the 3-cycle and one from the 5-cycle, so that gives us 3x5 spanning trees.
A note about the third row
To understand the final count that is given, we must note the duplication in the third row.  That is, the second and third graphs of the third row are mirror images and have equal counts of spanning trees.
This is reflected in the final count where 2(27+15) is added.  This reflects twice the counts for the reductions of the second graph in the third row (one contributes 27 and the other contributes 15), because the third graph in the third row has essentially the same pair of reductions.
