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.
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.
![[Snapshot]](HTMLImages/index.en/thumbnail_1.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_2.gif)
![[Snapshot]](HTMLImages/index.en/thumbnail_3.gif)
Browse all topics
