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.
On
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.
This area of graph theory is known as "graph reconstruction." The Reconstruction Conjecture (due to Kelly and Ulam) states that a graph (on at least 3 vertices) is determined by its multiset of subgraph obtained by deleting exactly one vertex. This multiset is called the deck of the graph. Kelly has a lemma that implies that you can compute the multiset of spanning trees from the deck of connected graphs. If a graph was determined by its multiset of spanning trees, then the reconstruction conjecture would be true for the graph.
It would be interesting to see if there are any graphs reconstructible from its deck but not its multiset of spanning trees.