Dissymmetry theorem for trees (source code)

= Dissymmetry theorem for trees

= Dissymmetry theorem
{synonym}

For finite nonempty <trees>, the <dissymmetry theorem for trees> gives an isomorphism of combinatorial classes
$$
\mathcal T+\mathcal T^{\to}=\mathcal T^{\bullet}+\mathcal T^{\text{edge}},
$$
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 $n$ distinctly labeled <vertices>, the counts reduce to $1+2(n-1)=n+(n-1)$. For unlabeled <trees>, symmetry makes the <bijection> essential: one cannot simply divide a rooted count by $n$.