The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math.research

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 346
Registered: 12/4/04
Re: Is "connected graphs" -> P(trees), G|->{spanning trees of G}

Posted: Mar 4, 2004 3:45 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
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.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.