Combining orthodoxy and xenology data in a common phylogenetic tree

A rooted tree T with vertex labels t (v) and set-valued edge labels λ (e) defines maps δ and ε on the pairs of leaves of T by setting δ (x, y) = q if the last common ancestor lca (x, y) of x and y is labeled q, and m ∈ ε (x, y) if m ∈ λ(e) for at least one edge e along the path from lca (x, y) to y. We show that a pair of maps (δ, ε) derives from a tree (T, t, λ) if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (Tδ, tδ ) that explains δ and the (unique) least resolved edge labeled tree (Tε, λε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.