# Is a graph $G$ completely determined (up to labelling) by its spanning trees?

The title is essentially the question. I know that trees can be represented as a topology (equivalently a topological closure operator) on a set -- so I'm wondering if the collection of spanning trees provides a "topological representation" of a graph (up to labelling of vertices).

Edit: As @dkuper pointed out a "topological" tree depends on the root --- making it more specific than a "graph" tree. I'm a topologist, not a graph theorist, so this is less interesting to me, but I think the question then essentially becomes: "Given a labelling of a graph $G$, when is $G$ the union of of its spanning trees?" A quick Google search doesn't say much, but this "seems" like a simple question.

• do you put the number of times each tree appears in the collection ? If this information is lost, then the statement is false (with for instace cycle and line of same length). Nov 19, 2013 at 13:17
• The trees would retain the labelling, would that do it? Nov 19, 2013 at 13:24
• It doesn't really make sense, you want to be invariant under relabelling. The question is interesting if you put each tree (up to isomorphism) in your collection, together with its multiplicity. Nov 19, 2013 at 13:25
• Basically, the different trees would be different topologies on the same set of elements. I think we need to retain some idea of how these topologies interact -- not just a count. I just mean, invariant up to coloring blue, for example. Perhaps my terminology for graph theory is not very good -- but does that make some sort of sense? Nov 19, 2013 at 13:42
• could you put a link to this topology via trees that you're referring to ? Nov 19, 2013 at 13:46