Figure 6
Illustration for the proof of Theorem 1. Given the label representation R(T1) = (L1, C1) and R(T2) = (L2, C2) of two trees, and a set of common node labels C ⊂ L1 ∩ L2, T1 can be transformed into T2 by deleting all nodes with labels in L1 \ (C, which implies deletion of all edges with source and target node labels in C1 \ (C1 ∩ C × C); inserting all nodes with labels in L2 \ C, deleting all edges with source and target node labels in (C1 ∩ C × C) \ C2; inserting all edges with source and target node labels in (C2 ∩ C × C) \ C1; and inserting all edges with source and target node labels in C2 \ (C2 ∩ C × C).