Is a graph determined by its multiset of spanning trees

combinatoricsgraph theorygraph-isomorphism

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.

Related Solutions

[Math] Spanning trees implies isomorphism

BIG HINT: Find non-isomorphic spanning trees of this graph:

            x---x---x  
            |   |   |  
            x---x---x

[Math] How many trees are in the spanning forest of a graph

You can think of each connected component as a graph by itself and talk about its associated spanning trees.

What it is saying is that you build a spanning forest by choosing a spanning tree from each connected component, therefore the number of trees in a spanning forest is the same as the number of connected components.

Best Answer

Related Solutions

[Math] Spanning trees implies isomorphism

[Math] How many trees are in the spanning forest of a graph

Related Question