Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Jim
Posts:
346
Registered:
12/4/04


Re: Is "connected graphs" > P(trees), G>{spanning trees of G} onetoone?
Posted:
Mar 4, 2004 3:45 AM


On Tue, 2 Mar 2004, sasha wrote:
> For a given natural number m, is the map > > connected graphs with m edges > power set of trees, > G > {spanning trees of G} > > onetoone?
If I'm not mistaken, you are essentially asking if we are given a set of spanning trees on n labeled vertices, we can always reconstruct the graph for which they (and only they) are spanning trees of. Consider the union of all edges in all the spanning trees in some given set of trees. Then we have a graph for which all those trees are spanning trees of. If there was another (different) graph, then it must differ at some edge i.e. it must have an edge that is not in one of those spanning trees. So, ask yourself: in any graph G, does G have an edge which can not be in any spanning tree of G?
> And the more general map > connected graphs> power set of trees, > G > {spanning trees of G}?
The above argument should work on this case as well.
> For simplicity, we assume that the nodes are always the first n natural > numbers, for a convenient n. > And how about graphs up to isomorphy?
I assume you are now ignoring any vertex labels. Then take G to be a 4cycle. In the labeled case, it would have spanning trees 1234, 2341, 3412, 4123. But if we are ignoring vertex labels, then it has one spanning tree: namely, a path on 4 vertices. Note that other graphs (like the path on 4 vertices) have the same set of spanning tree(s). So the answer in this case (if my interpretation of what you meant if correct) is no.
J



