The answer is was given by David Eisenstadt in his answer to my question.
The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).
While I don't fully understand everything about this problem, the intuitive reasoning is as follows:
Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.
If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.