# Generate all spanning trees of the complete graph

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?

• BTW the random sampling technique you mentioned is implemented in IGRandomSpanningTree Mar 27, 2020 at 11:03

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]
` • Nice one! I didn't know about these Prüfer sequences. I had thought IGraph would be good here.
– apg
Mar 27, 2020 at 9:05