4
$\begingroup$

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?

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

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]

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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