# Visualizing Cayley's Formula in Mathematica

Cayley's formula tells us that the number of labeled trees with $$n$$ vertices is $$n^{n-2}$$. Here is Wikipedia's visualization for $$n=2,3,4$$.

How can we use Mathematica to visualize cases where $$n > 4$$?

I have upvoted @Szabolcs answer. I am sure there are better code to tree approaches than mine in the following. IGraphM is ideal as Szabolcs illustrates. I post this just to extend visualization for $$n>4$$ case.

Happy New Year to all MSE users

Just some visualization options:

fun[code_] :=
Module[{v = Range[Length[code] + 2], cd = code, e = {}, c},
While[Length[v] != 2,
c = Sort[Complement[v, cd]];
AppendTo[e, {cd[[1]], c[[1]]}];
v = DeleteCases[v, c[[1]]];
cd = Drop[cd, 1];];
Graph[UndirectedEdge @@@ AppendTo[e, v], VertexSize -> 0.3,
VertexLabels ->
Table[i -> Placed[Style[i, White, Bold], {1/2, 1/2}], {i,
v[[-1]]}],
VertexStyle ->
Table[i -> ColorData["Rainbow"][i/v[[-1]]], {i, v[[-1]]}]]]
disp[n_] :=
Grid[Partition[Column[{#, fun[#]}] & /@ Tuples[Range[n], n - 2], n],
Frame -> All]
man[u_] :=
Manipulate[fun[{##}[[All, 1]]], ##, ControlType -> SetterBar] & @@
Table[{Symbol["x" <> ToString[i]], Range[u]}, {i, u - 2}]


So, disp[4]:

And man[10] (note this is inspired by this Wolfram Demonstration but generalizes the visualization and I do not use the same code for creating tree from Prufer code). :

• ubpdqn: Wonderful answer. Out of curiosity: did you make the video of you mousing over man[10] with Mathematica, or another tool? – George Dec 31 '19 at 16:30
• @George ScreenToGIF – ubpdqn Dec 31 '19 at 22:24
• Happy New Year to all – ubpdqn Dec 31 '19 at 22:25

You can use Prüfer sequences to generate all labelled trees. IGraph/M has the required functionality.

coloredPruferTree[p_] :=
IGFromPrufer[p, GraphStyle -> "BasicBlack", VertexSize -> 1/4] //
IGVertexMap[ColorData[97], VertexStyle -> VertexList]

allTrees[n_] :=
coloredPruferTree /@ Tuples[Range /@ ConstantArray[n, n - 2]]


Now you can list all labelled trees on 3 vertices:

allTrees[3]


Or 4 vertices:

allTrees[4]


Furthermore, you can group the trees by isomorphism class using

allTrees[5] // GroupBy[CanonicalGraph] // Values

• A tiny comment on German orthography: When you don't have access to Umlaut characters, don't just leave out the Umlaut but replace it by a letter E. So Prüfer becomes Pruefer without Umlaut. That said, fantastic work Szabolcs! – Roman Dec 31 '19 at 11:55
• @Roman Do you mean in the function name? I actually thought for a while about whether to use IGFromPrufer or IGFromPruefer, then did a search to see what most other systems use. None of the ones I found were using Pruefer so I went with Prufer ... But then many of them don't even spell Prüfer correctly in their documentation, so perhaps I should have consulted a native German speaker. (In text / documentation I made sure to always put on the umlaut. I do care about it as Hungarian has it too.) – Szabolcs Dec 31 '19 at 12:39
• Yes, like GroebnerBasis computes the Gröbner basis, MandelbrotSetBoettcher and JuliaSetBoettcher the Böttcher function, MoebiusMu the Möbius function, etc. – Roman Jan 9 at 18:45