TAOCP 2.3.4.2 Exercise 8
Let $G$ be a finite or locally finite oriented tree in which every vertex $v\neq R$ has exactly one outgoing arc and the root $R$ has no outgoing arc.
Section 2.3.4.2: Oriented Trees
Exercise 8. [**] $$HM40$$ Study the properties of automorphism groups of oriented trees, namely the groups consisting of all permutations $\pi$ of the vertices and arcs for which we have $\operatorname{init}(e\pi)=\operatorname{init}(e)\pi$, $\operatorname{fin}(e\pi)=\operatorname{fin}(e)\pi$.
Verified: yes
Solve time: 2m06s
Let $G$ be a finite or locally finite oriented tree in which every vertex $v\neq R$ has exactly one outgoing arc and the root $R$ has no outgoing arc. Write $P(v)$ for the unique vertex with an arc $v\to P(v)$. Thus $P(R)$ is undefined and every other vertex has exactly one parent.
An automorphism $\pi$ is a permutation of vertices and arcs satisfying
$$ \operatorname{init}(e\pi)=\operatorname{init}(e)\pi,\quad \operatorname{fin}(e\pi)=\operatorname{fin}(e)\pi. $$
1. The root is fixed
The root $R$ is the unique vertex with out-degree $0$. Since automorphisms preserve out-degree, $\pi(R)=R$.
2. Automorphisms preserve the parent structure
If $v\to P(v)$ is the unique outgoing arc from $v$, then applying $\pi$,
$$ \pi(v)\to \pi(P(v)) $$
is an outgoing arc from $\pi(v)$. By uniqueness of outgoing arcs, this must be the outgoing arc from $\pi(v)$, hence
$$ P(\pi(v))=\pi(P(v)). $$
Thus $\pi$ commutes with the parent function.
For each vertex $v$, define the rooted subtree $T_v$ consisting of all vertices $u$ whose iterated parent chain eventually reaches $v$, with root $v$.
We first prove:
Lemma 1. For every vertex $v$,
$$ \pi(T_v)=T_{\pi(v)}, $$
and the restriction $\pi|{T_v}:T_v\to T{\pi(v)}$ is an isomorphism of rooted oriented trees.
Proof. We use induction on distance from $v$. The statement holds for $v$ itself. If $u\in T_v$, then repeated application of $P(\pi(u))=\pi(P(u))$ shows that the parent chain of $\pi(u)$ reaches $\pi(v)$, so $\pi(u)\in T_{\pi(v)}$. The same argument applied to $\pi^{-1}$ gives equality of sets. Edge preservation follows from preservation of $\operatorname{init},\operatorname{fin}$. ∎
Hence automorphisms map rooted subtrees isomorphically onto rooted subtrees.
3. Structure at a vertex
Fix a vertex $v$. Let
$$ C(v)={u : P(u)=v} $$
be the set of children of $v$. Each $u\in C(v)$ determines a rooted subtree $T_u$.
Define an equivalence relation on $C(v)$ by
$$ u \sim u' \iff T_u \cong T_{u'} \text{ as rooted oriented trees}. $$
Let the equivalence classes be $C_1(v),\dots,C_k(v)$.
4. Necessary structure of an automorphism
Let $\pi$ be an automorphism. From Lemma 1:
- $\pi$ maps $C(v)$ bijectively onto $C(\pi(v))$,
- and if $u\in C(v)$, then $T_u \cong T_{\pi(u)}$.
Therefore $\pi$ induces, for each $v$, a bijection
$$ C(v)\to C(\pi(v)) $$
that preserves isomorphism classes of rooted subtrees.
Moreover, within each class $C_i(v)$, $\pi$ permutes vertices arbitrarily subject only to mapping into the corresponding class in $C(\pi(v))$.
Also, once $\pi(u)$ is fixed, Lemma 1 forces $\pi$ to restrict to an automorphism $T_u \to T_{\pi(u)}$. Thus the action on different subtrees is fully determined locally.
This proves that every automorphism yields a consistent family of:
- permutations of each class $C_i(v)$,
- and induced automorphisms on each rooted subtree.
5. Sufficiency: constructing an automorphism from local data
We now prove the converse: any consistent choice of such local permutations and subtree automorphisms defines a unique global automorphism.
We proceed by induction on depth from the root.
Construction.
- Define $\pi(R)=R$.
- Assume $\pi$ is defined on all vertices at depth $\le d$ and preserves parent relations there.
Let $v$ be a vertex at depth $d$. For each child $u\in C(v)$, choose:
- a target child $\sigma_v(u)\in C(\pi(v))$ such that $u\sim u'$ implies $\sigma_v(u)\sim \sigma_v(u')$,
- an isomorphism of rooted trees $\varphi_u:T_u\to T_{\sigma_v(u)}$.
Define $\pi(u)=\sigma_v(u)$, and for every descendant $x\in T_u$, define
$$ \pi(x)=\varphi_u(x). $$
6. Well-definedness and independence
Two issues must be checked:
(i) No conflicts between subtrees.
The sets $T_u$ for distinct children $u\neq u'$ of $v$ are disjoint. Hence definitions on different subtrees do not overlap.
(ii) Compatibility with parents.
If $x\in T_u$, then $P(x)\in T_u$ as well. Since $\varphi_u$ is a rooted-tree isomorphism,
$$ \varphi_u(P(x)) = P(\varphi_u(x)), $$
so the parent relation is preserved inside each subtree. At the boundary,
$$ P(u)=v \implies P(\pi(u))=\pi(v), $$
by construction of $\sigma_v$. Hence parent preservation holds globally.
Thus $\pi$ is a well-defined endomorphism of the vertex set preserving adjacency and orientation.
7. Bijectivity
Each $\varphi_u$ is a bijection between $T_u$ and $T_{\sigma_v(u)}$, and the collection ${T_u}_{u\in C(v)}$ partitions all descendants of $v$. Since the construction matches these blocks bijectively at every level, $\pi$ is bijective on each finite depth layer, hence on all vertices. Therefore $\pi$ is a permutation of vertices, and similarly of arcs.
8. Homomorphism property
By construction, every arc $x\to P(x)$ is mapped to
$$ \pi(x)\to \pi(P(x)), $$
so $\pi$ preserves the functions $\operatorname{init}$ and $\operatorname{fin}$. Hence $\pi$ is an automorphism.
9. Bijection between constructions and automorphisms
- Injectivity: Different choices at some vertex $v$ change either $\pi(v)$ or the image of some subtree, so they produce different global maps.
- Surjectivity: Every automorphism yields exactly the local permutations and subtree automorphisms described in Sections 3–4.
Thus the construction is in bijection with the automorphism group.
10. Structural description
Recursively, the automorphism group at a vertex $v$ is a product of:
- symmetric groups permuting isomorphic child subtrees at $v$,
- semidirectly combined with automorphism groups of each subtree.
Inductively this yields an iterated wreath-product decomposition along the rooted structure of the tree.
This completes a rigorous characterization of the automorphism group of oriented trees. ∎