From: Robin Chapman Newsgroups: comp.theory,sci.math Subject: Re: A question on graphs Date: Fri, 10 Jul 1998 12:51:20 GMT In article <6o2cq5$pmj@catapult.gatech.edu>, ae37@acmex.gatech.edu (Ayman M. Elsaedi) wrote: > Hi, > I have this three part question: > 1. I know that the number of labeled trees on n verteces is n^(n-2). My > question is, is there a way for proving that without using Lagrange > Inversion? Yes. There are many ways of proving this. One of the best-known is that of Pr"ufer, who sets up a bijection bewteen the set of labelled trees on {1,2,...,n} and the set of ordered (n-2)-tuples from {1,2,...,n}. For each such tree we define its Prufer code as follows: repeat the following prccedure n-2 times: (i) find the leaf with least label: a say, and let b be its adjacent vertex. (ii) write down b (iii) delete b and the edge ab from the tree. The n-2 numbers produced give the Prufer code. To show this is a bijection one needs the reverse construction. Suppose you are given an (n-2)-tuple C. Write down a list L of all numbers from 1 to n inclusive. Repeat the following step n-2 times: find the least number a occuring in L but not in C, then join vertex a to b, the first entry of C, then delete a from L and the first entry b from C. After this one has two elements left in L, c and d say. Finish by joining c to d. For details (and another proof due to Clarke) see Robin Wilson's Introduction to Graph Theory. For yet another method (due to Joyal) see Peter Cameron's book on Combinatorics. > 2. How many unlabeled trees are there for n vertices? > 3. Any references to an algorithm which can produce all such trees? These are much harder :-( Robin Chapman + "They did not have proper Department of Mathematics - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum