A combinatorial construction for twin trees (Q1911839)

A tree is a connected graph without cycles. A twin tree \((T^+, T^-, \text{cod})\) is a pair of trees \(T^+\), \(T^-\) with a function \(\text{cod}: T^+\times T^-\cup T^-\times T^+\to \mathbb{Z}\) satisfying (1) \(\text{cod}(x, y)\geq 0\); (2) \(\text{cod}(x, y)= \text{cod}(y, x)\); (3) if \(x'\) is adjacent to \(x\), then \(|\text{cod}(x', y)- \text{cod}(x, y)|= 1\); (4) if \(\text{cod}(x, y)\neq 0\), then for exactly one vertex \(x'\) adjacent to \(x\), \(\text{cod}(x', y)= \text{cod}(x, y)+ 1\) holds. If the valencies of all vertices in \(T^+\) and \(T^-\) are greater than 2, the trees are necessarily isomorphic, and, since any tree is bipartite, in one class of valency \(k\) and in the other class of valency \(\ell\), for some \(k\) and \(\ell\). Many properties for twin trees are discussed. Particularly, a construction for all twin trees is given. The paper proves that for any pair \((k, \ell)\) of integers greater than 2, there is a continuum infinite set of twin trees with these valencies.