Is it known whether a (connected) graph is determined by its multiset of spanning trees? In other words, do any two non-isomorphic connected graphs have different multisets of spanning trees? By a multiset I mean the set of spanning trees (up to isomorphism) and the counts of how many times each occurs.

I cannot find counterexamples or positive results on this.

I see that a previous post has asked this question without considering the counts of each spanning tree.

## Best Answer

I just found an example in the graph reconstruction literature (thanks Bob Krueger) of two non-isomorphic graphs that have the same multiset of spanning trees, in Sedlacek, J. (1974). The reconstruction of a connected graph from its spanning trees. Mat. Casopisâ€™Sloven. Akad. Vied. 24, 307-314. They are depicted below.

Also, they can be distinguished by their decks of node-deleted subgraphs, as the left graph has an 8-cycle as a node-deleted subgraph, while the right graph does not.