Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Is "connected graphs" -> P(trees), G|->{spanning trees of G} one-to-one?
Replies: 6   Last Post: Mar 15, 2004 11:00 AM

 Messages: [ Previous | Next ]
 Jim Posts: 346 Registered: 12/4/04
Re: Is "connected graphs" -> P(trees), G|->{spanning trees of G}
one-to-one?

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}
>
> one-to-one?

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 4-cycle. In the labeled case, it would have spanning trees
1-2-3-4, 2-3-4-1, 3-4-1-2, 4-1-2-3.
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

Date Subject Author
3/2/04 sasha
3/4/04 Jim
3/4/04 Dan Luecking
3/5/04 Dan Luecking
3/15/04 Arnaldo Mandel
3/10/04 Alexander Malkis