Lagmental Vicfred

Rooted-Tree Subtree Sizes Obey a Bottom-Up Recurrence by Vicfred

Last updated: Thu 23 May 2024

tags: mathematics, trees, graph distance, structural graph theory

A subtree contains its root plus the disjoint subtrees of all children. I want the notation, the mechanism, and the failure mode visible at the same time.

Statement

A finite graph \(T=(V,E)\) is a tree when it is connected and acyclic. The unique simple path \(P_{uv}\) between two vertices makes distance and recursive decomposition especially rigid.

$$ \operatorname{sub}(v)=\#\{u:v\text{ is an ancestor of }u\} $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ \operatorname{sub}(v)=1+\sum_{u\in\operatorname{child}(v)}\operatorname{sub}(u) $$

Worked algebra

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \begin{array}{c}v\\[-2pt]\diagdown\quad\diagup\\u_1\qquad u_2\end{array}\quad\Longrightarrow\quad\operatorname{sub}(v)=1+\operatorname{sub}(u_1)+\operatorname{sub}(u_2) $$

Conceptual compression

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad \operatorname{sub}(v)=\#\{u:v\text{ is an ancestor of }u\},\\[5pt] \mathsf{C}\;&:\quad \operatorname{sub}(v)=1+\sum_{u\in\operatorname{child}(v)}\operatorname{sub}(u). \end{aligned} $$

Caveat

A rooted tree adds a parent relation that an unrooted tree does not possess. Statements about ancestors depend on the chosen root.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{sub}(v)=1+\sum_{u\in\operatorname{child}(v)}\operatorname{sub}(u) \end{gathered}} $$

A symbolic summary is trustworthy only because the example and limitation remain visible beside it. The box compresses the conclusion without hiding its origin.

This article was posted on Fri 05 January 2024. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.