Generate random trees without degree-2 vertices

Question

I am looking for algorithms for the uniform sampling of labelled trees on $n$ vertices with the constraint that none of the vertices should have degree 2. Are there any results for this problem?

Such trees have a Prüfer sequence in which no entry appears precisely once.

For clarification, and example of such a tree is:

Answer 1

One approach is the following:

1. Pick a uniformly random tree on $n+k$ vertices (we'll pick $k$ later).
2. If the number of degree-$2$ vertices is not $k$, start over.
3. For each vertex of degree $2$, replace it by an edge between its endpoints, until there are no such vertices left.
4. Change the labels from a subset of $\{1,2, \dots, n+k\}$ to $\{1,2,\dots,n\}$, preserving their order.

The result is going to give a uniformly random tree with the constraint, because in each $n$-vertex tree, there are $\binom{n+k}{n}$ ways to undo step 4, and $(n-1)n(n+1)(\dots)(n+k-2)$ ways to undo step 3 (for each vertex of degree 2, in order from smallest to largest, pick an edge to insert it on). So each $n$-vertex tree can be obtained in the same number of ways.

(I guess, equivalently, we could choose a random Prüfer code for an $(n+k)$-vertex tree, and delete the entries that only show up once, changing the labels of the rest in the same way as before. We'd have to be careful to distinguish labels that appeared $0$ times from labels that appeared $1$ time that we deleted, when we relabel.)

The tricky part is choosing $k$. Each label occurs exactly once in the Prüfer code with probability approximately $\frac 1e$, so the expected number of vertices of degree $2$ is approximately $\frac{n+k}{e}$. This makes it reasonable to choose $k = \lfloor \frac n{e-1}\rfloor$, for example.

The probability of getting exactly $k$ degree-$2$ vertices can be approximated by $\Pr[\text{Binomial}( n+k, \frac1e) = k]$, which is $O(\frac{1}{\sqrt n})$. This is not quite true, because the degrees are not independent, but still suggests that only $O(\sqrt n)$ trials are needed.

---

Here's a simple implementation using IGraph/M in Mathematica:

sample[n_] := IGTryUntil[VertexCount[#] == n &] @ IGSmoothen @ IGTreeGame[n + Floor[n/(E - 1)]]

A faster, but somewhat less simple version:

sample2[n_] := 
  With[{k = Floor[n/(E - 1)]},
    IGSmoothen @ IGTryUntil[Count[VertexDegree[#], 2] == k &] @ IGTreeGame[n + k]
  ]