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 ]
 Arnaldo Mandel Posts: 11 Registered: 12/12/04
Re: Is "connected graphs" -> P(trees), G|->{spanning trees of G} one-to-one?
Posted: Mar 15, 2004 11:00 AM

Dan Luecking <Look-In-Sig@uark.edu> writes:

> On Thu, 04 Mar 2004 11:56:49 -0600, Dan Luecking <Look-In-Sig@uark.edu>
> wrote:
>

> >On Tue, 2 Mar 2004 20:20:59 +0100, "sasha"
> ><sashaLOESCHEDIESmal.REMOVEITexcite.com@news.sdt.net (AT)> wrote:
> >

> >>Hello everyone!
> >>
> >>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?

> >
> >Yes, for simple graphs. No, if loops or parallel edges are allowed:
> >a graph with one loop and one simple edge has the same spanning tree
> >as a graph with two edges connecting the same 2 vertices.

>
> Oops. I suppose the latter has two spanning trees corresponding to
> the two parallel edges. Replace this example with: G1 has a loop at x
> and an edge from x to y. While G2 has an edge from x to y and a loop
> at y.

Actually, this is far from true. Perhaps the simplest example is

o o
/ \ / \
o---o o---o---o
| | and | \ /
o---o o-----o
\ /
o

(label the edges so that triangles get the same sets of labels).

What really occurs is explained by an old theorem of Whitney, characterizing
when two graphs have the same matroid.

For 3-connected graphs the statement is true, and easy to prove if you have
some matroid concepts at your fingertips.

For 2-connected graphs, Whitney's Theorem shows how to transform one graph
into the other.

For graphs that are not 2-connected, there must exist a 1-1 correspondence
between blocks preserving trees.

--
Arnaldo Mandel
Departamento de CiÃªncia da ComputaÃ§Ã£o - Computer Science Department
am@ime.usp.br
Talvez vocÃª seja um Bright http://the-brights.net Maybe you are a Bright.

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