Common NVB refinement and overlay cardinality

Let $F_i$ be the finite binary forest for ${\mathcal{T}}_i$. Their node union $F=F_1\cup F_2$ is a forest: every nonroot node keeps its parent, and a node is either a leaf in both forests or has its same two children in at least one; if it has children in either forest, the union contains both. The common initial edges have equal labels. Induct on the bisection depth of any shared edge: its midpoint is uniquely determined by the segment, and its two half-edge labels are determined by the same generation rule [F1]; therefore both incident forests prescribe the same descendants on that edge. The leaves of $F$ consequently form a matching conforming triangulation refining both ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$. Any common refinement must contain every node split in either forest, so it contains $F$ and refines its leaf partition. Thus this is the smallest common conforming overlay.

For each initial root, a finite full binary tree with $i$ internal nodes has $i+1$ leaves; induction on $i$ proves this because splitting one leaf increases the leaf count by one. The internal nodes of $F$ are the union of the internal nodes of $F_1,F_2$, so $\mathrm{\#}\mathrm{Int}(F)\le \mathrm{\#}\mathrm{Int}(F_1)+\mathrm{\#}\mathrm{Int}(F_2)\mathrm{.}$ Summing the leaf identity over the $\mathrm{\#}{\mathcal{T}}_0$ roots gives $\mathrm{\#}{\mathcal{T}}_i=\mathrm{\#}{\mathcal{T}}_0+\mathrm{\#}\mathrm{Int}(F_i)$ and the same identity for the overlay. Substitution proves the inequality.