For finite nonempty trees, the dissymmetry theorem for trees gives an isomorphism of combinatorial classes
where the superscripts mark a vertex, an undirected edge, or a directed edge. The tree on each side retains the same labels or other decorations; the identity is stronger than a count of labeled trees.
Repeatedly remove all leaves until one vertex or one edge remains. This is the invariant center of a tree. If a marked vertex or edge is the center, forget the mark and obtain the unrooted tree. Otherwise use the unique path toward the center: a marked vertex determines the first edge oriented toward the center, while a marked edge is oriented away from the center. These assignments give all directed-edge marks exactly once and can be reversed from the center and the orientation. This supplies the required bijection.
For a fixed tree with distinctly labeled vertices, the counts reduce to . For unlabeled trees, symmetry makes the bijection essential: one cannot simply divide a rooted count by .

Articles by others on the same topic (0)

There are currently no matching articles.