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?

  • 1
    $\begingroup$ BTW the random sampling technique you mentioned is implemented in IGRandomSpanningTree $\endgroup$
    – Szabolcs
    Mar 27, 2020 at 11:03

1 Answer 1


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

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


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

enter image description here

  • $\begingroup$ Nice one! I didn't know about these Prüfer sequences. I had thought IGraph would be good here. $\endgroup$
    – apg
    Mar 27, 2020 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.