= 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$.
Back to article page