Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following desiderata:


D1. $f(T)$ is a (random) tree on the vertex set $V'=\lbrace 1,\ldots,n+1\rbrace$;


D2. the distribution of $f(T)$ is uniform over the set of all $(n+1)^{n-1}$ labeled trees on $V'$;


D3. $f$ is a simple graph-theoretic recipe.


This $f$ can be a random function. That is, it can flip coins in deciding what to do with $T$: for instance, removing an edge uniformly at random.


One obvious way to satisfy D1 and D2 is: 


1. convert $T$ to its Prüfer sequence $s$;
2. independently, with probability $1/(n+1)$, change each entry of $s$ to $n+1$ (otherwise leave it fixed);
3. then add a random number to the end of $s$, drawn uniformly from $V'$;
4. let $f(T)$ be the tree corresponding to the new sequence.


But what this procedure "really does" to $T$ seems not so easy to describe in graph-theoretic terms. I am looking for a recipe that satisfies D1-3 by manipulating the graph "directly" (i.e., adding and removing edges) without opaque steps like (1) and (4) in the above procedure.



Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?
This is an interesting question. For any fixed positive integer $d \geq 2$, write $T\_d^{\infty}$ 
for the complete infinite rooted $d$-ary tree (by this I mean every node has exactly $d$ children). [Luczak and Winkler](http://onlinelibrary.wiley.com/doi/10.1002/rsa.20011/abstract) proved the existence of a procedure which will generate a sequence $(T\_{n,d})\_{n \geq 0}$ such that for all $n \geq 1$, 


(a) the distribution of T\_{n,d} is uniformly random over all $n$-node subtrees of $T^{\infty}\_d$ that contain the root of $T^{\infty}\_d$; and 


(b) $T\_{n,d}$ is a subtree of $T\_{n+1,d}$. 


It is not hard to show that (a) implies that for all $n$, $T\_{n,d}$ is distributed as a Galton-Watson tree with offspring distribution $\mathrm{Bin}(d,1/d)$, conditioned to have total size $n$. 
Since $\mathrm{Bin}(d,1/d)$ tends to a $\mathrm{Poisson}(1)$ distribution as $d$ becomes large, 
this means that as $d \to \infty$, the distribution of $T\_{n,d}$ tends to that of a Galton-Watson tree with offspring distribution $\mathrm{Poisson}(1)$ conditioned to have $n$ nodes (let me write $\mathrm{PGW}\_n(1)$ for this distribution). The latter distribution is the same as that of a uniformly random labelled rooted tree on labels $1,\ldots,n$. (At least, the latter is true once we label the Galton-Watson tree uniformly at random, or alternately remove the labels of the labelled rooted tree.)


As noted by [Lyons et al.](http://arxiv.org/abs/0711.1893) (Theorem 2.1), all this implies in particular that one can define a similar sequence $(T\_n)\_{n \geq 1}$ such that for all $n$, $T\_n$ is a subtree of $T\_{n+1}$ and $T\_n$ has distribution $\mathrm{PGW}\_n(1)$. 


However, the construction in the Luczak-Winkler paper uses flows, and it is not 100% obvious how it "passes through to the $d=\infty$ limit." (I say this with the caveat that I didn't make any serious attempt at figuring this out.) As a consequence, while it is known that there exists a generation procedure of the type you are looking for, I am not aware of an explicit description of the actual rule for where the leaf should be attached to $T\_n$ to create $T\_{n+1}$. I asked Peter Winkler about this at a conference last year and he also didn't know (though I don't know whether he had thought about this specific question in depth, either). 


