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

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 ]
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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Dan Luecking <> writes:

> On Thu, 04 Mar 2004 11:56:49 -0600, Dan Luecking <>
> wrote:

> >On Tue, 2 Mar 2004 20:20:59 +0100, "sasha"
> >< (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
\ /

(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
Universidade de São Paulo, Bra[sz]il
Talvez você seja um Bright Maybe you are a Bright.

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-2017. All Rights Reserved.