For finite nonempty trees, the dissymmetry theorem for trees gives an isomorphism of combinatorial classeswhere 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.
Articles by others on the same topic
There are currently no matching articles.