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



Re: Is "connected graphs" > P(trees), G>{spanning trees of G} onetoone?
Posted:
Mar 15, 2004 11:00 AM


Dan Luecking <LookInSig@uark.edu> writes:
> On Thu, 04 Mar 2004 11:56:49 0600, Dan Luecking <LookInSig@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} > >> > >>onetoone? > > > >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 / \ / \ oo ooo   and  \ / oo oo \ / 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 3connected graphs the statement is true, and easy to prove if you have some matroid concepts at your fingertips.
For 2connected graphs, Whitney's Theorem shows how to transform one graph into the other.
For graphs that are not 2connected, there must exist a 11 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 am@ime.usp.br Talvez vocÃª seja um Bright http://thebrights.net Maybe you are a Bright.



