Prüfer Codes of Labeled Trees

In 1889, Cayley proved that there are labeled trees on nodes. In 1918, Prüfer found a method for constructing each tree.
Consider the tree with code {2, 8, 9, 4, 7, 7, 2} that is given as the default tree in this Demonstration. The first digit of the Prüfer code is the branch that has the smallest isolated number. Pruning that branch gives a new tree, and the process repeats, as shown in the Details.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The smallest non-branch number is 1. Cut it from 2.
The smallest non-branch number is 3. Cut it from 8.
The smallest non-branch number is 5. Cut it from 9.
The smallest non-branch number is 6. Cut it from 4.
The smallest non-branch number is 4. Cut it from 7.
The smallest non-branch number is 8. Cut it from 7.
The smallest non-branch number is 7. Cut it from 2.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.