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 5, 2004 6:39 PM


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.
One should always be clear what "different" and "same" mean. I clearly wasn't.
Dan
 Dan Luecking Department of Mathematical Sciences University of Arkansas Fayetteville, Arkansas 72701 To reply by email, change LookInSig to luecking



