Generate all spanning trees of the complete graph

Question

How can you use Mathematica to generate all the spanning trees of the complete graph?

One can count the spanning trees of a connected graph ${G}$ using e.g. the Tutte polynomial $T_{G}(1,1)$. For the complete graph $K_{n}$, the count is $T_{K_{n}}=n^{n-2}$. But this does not generate them.

One way is to use e.g. Wilson's algorithm, and reject new picks if the new pick is identical to a previous pick, until you have $n^{n-2}$ different spanning trees. But this requires randomly picking trees. Is there a better way?

Answer 1

You mean, generate all labelled trees on $n$ vertices.

Generate all Prüfer sequences and convert them to trees with IGraph/M.

Needs["IGraphM`"]

n = 4;
IGFromPrufer[#, VertexShapeFunction -> "Name"] & /@ Tuples[Range[n], n - 2]