I was reading about Cayley's formula for the number $T_n$ of labelled trees with $n$ vertices .The book describes a way for finding a formula for $T_n$" The solution basically goes this way:
A tree is a non oriented graph without a cycle . It is called labelled if all the vertices are numbered. A labelled tree with one vertice is just a point . It can only be labelled in one way. There is also just one labelling with two vertices.In case of three vertices the labelling is three for the middle vertex and the other two are indistinguishable. In case of four points, we have two topologies:a chain of $4$ points has $12$ distinct labellings and a ring of $4$ vertices has $4$ choices for the middle point , thus all total $16$ different labellings are there for a tree with $4$ vertces.
However, I want to know about a much crucial but basic idea (fundamental for solving this problem):
1.How do we draw a tree with a specified no. of vertices (say , $n$ ) in all configurations possible?
Well, I mean if we have 4 vertices then we know that one configuration will be surely a straight chain and by working out a bit ...drawing the points we can conclude that the other possible conguration is a star ...but what about $5$ vertices ...how do we get all possible configurations...is there a way of deciding it?If yes, I do want to know that.
- Let's say we do find all configurations fir a given no. of vertices...then how do we label if for say, ...when total no. of vertices is $5$ or $6$ or $7$ ... In case of $4$ vertices we can do it by drawing up a chain then we find among those points in the chain there are $4$ choices for the end point vertex on one side of the chain and then we have $3$ vertex left so we already know $3$ chain vertex has $3$ labellings so then $4$ chain vertex we have $4.3=12$ labellings . I solved for a $4$ vertices chained tree ...and for the ring topological case we can see that the middle point has $4$ labellings possible and hence the remaining three points surrounding it are indistinguishable for one particular labelling of the middle point as if we observe that case more closely then for that particular choice of middle point vertex in the tree all the other arrangements of the numbered labels are basically inverted or flipped images of each other and so they basically is equaivalent to one configuration for a particular choice of the label for the middle point.But now tbe question arises for much higher configuration ,lets say a tree with $7$ vertices...how can we find all configurations and do the labelling for other cases (as may be possible)...as for that we need all the configurations ...But even if we get all the other configurations then how do we get the labellings possible for each configurations...which means I basically need an example for a 6 no. tree (tree with 6 vertices) and list all configurations and then case by case deal with the ways of labelling each of them...
3.How do we verify the Cayley's formula for the number of distinct labellings of a tree $T_n$ with $n$ vertices using Prüffer code (and other bijective techniques ) ...I am not familiar with Prüffer code and the encoding and decoding algorithm( which eventually brings out the bijective proof)...