Mathematical Recreations : Homeomorphically Irreducible Trees of size n=10

A homeomorphically irreducible tree is an acyclic graph where there are more than two branches from each internal vertex. The size n=10 means there are ten vertices, internal or edge, in the tree.

A. Homeomorphic irreducible trees of n=10.

In the movie "Good Will Hunting", the puzzle of calculating all of such trees with a total of ten vertices was presented to a class as a difficult challenge that took a couple years to calculate.  The puzzle came to my attention after watching a Numberphile video on youtube, where the guest mathematician rightly pointed out that it really isn't that difficult of a puzzle as he drew out all ten possibilities.

There are lots of blog posts pointing out how simple the problem actually is, but neither the Numberphile mathematician or any of the various bloggers point out how the ten possibilities are connected by a set of very simple transformations.

B. Transformation rules.

The first transformation (fig B1) takes three leaves (edge vertices) from an internal vertex and generates a new internal vertex with two leaves.

The second transformation (fig B2) moves a leaf from one internal vertex to another.

You can't apply a transformation such that it will generate a tree with only two branches from an internal vertex, as the resulting tree will no longer be homeomorphically irreducible.

C. Transformation relationships.

With these transformations, it is a simple task to generate all the possible homeomorphically irreducible trees for higher numbers of vertices. (At least for every case that I've examined.) You start with the simplest case of the pinwheel and apply as many of the transformations as you can at each step until you run out of steps. Proving that this process will generate all possibilities for any number of vertices is a more difficult challenge.

I suspect there might be a set of such trees where individuals are isolated from others, where another transformation would be required.

D. Transformation graph.

The map of trees connected by transformations generates a new graph (such as fig D). My limited scribbling of the trees for a set of 11 and 12 nodes shows that there is more than one valid transformation graph for some sets of trees. I'll have to explore the properties of these transformation graphs further at some point.