# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 3 Best Match Graphs, Least Resolved Trees, and Binary-Explainable BMGs  
In this section, we first summarize some properties of best match graphs and their least resolved trees. We then show that the contraction of inner edges in least resolved trees always leads to least resolved trees. Furthermore, we recall some properties of binary-explainable best match graphs that will be needed later. Definition 1: Let \((T,\sigma)\) be a leaf-colored tree. A leaf \(y\in L(T)\) is a _best match_ of the leaf \(x\in L(T)\) if \(\sigma(x)\
eq\sigma(y)\) and \(\operatorname{lca}_{T}(x,y)\preceq_{T}\operatorname{lca}_{T}(x,y^{\prime})\) holds for all leaves \(y^{\prime}\) of color \(\sigma(y^{\prime})=\sigma(y)\). Given \((T,\sigma)\), the digraph \(G(T,\sigma)=(V,E)\) with vertex set \(V=L(T)\), vertex-coloring \(\sigma\), and with \(\operatorname{arcs}(x,y)\in E\) if and only if \(y\) is a best match of \(x\) w.r.t. \((T,\sigma)\) is called the _best match graph_ (BMG) of \((T,\sigma)\)[1]:  
Definition 2: An arbitrary vertex-colored digraph \((G,\sigma)\) is a _best match graph_ (BMG) if there exists a leaf-colored tree \((T,\sigma)\) such that \((G,\sigma)=G(T,\sigma)\). In this case, we say that \((T,\sigma)\) explains \((G,\sigma)\). Proposition 1 ([16], Lemma 8): _If \(T_{A}\) is obtained from a tree \(T\) by contracting all edges in a subset \(A\) of inner edges in \(T\), then \(G(T,\sigma)\subseteq G(T_{A},\sigma)\)._  
An edge \(e\) of a leaf-colored tree is _redundant_ (w.r.t. \((G,\sigma)\)) if it can be contracted without affecting the BMG, i.e., if \(G(T,\sigma)=G(T_{e},\sigma)\). Definition 3: A leaf-colored tree \((T,\sigma)\) is _least resolved_ if there is no non-empty subset \(A\subseteq E(T)\) such that \(G(T,\sigma)=G(T_{A},\sigma)\). We define the notion of being least resolved here as a property of the tree \((T,\sigma)\) alone. Of course, every least resolved tree is also _least resolved w.r.t. some BMG_, namely, the (uniquely defined) digraph \(G(T,\sigma)\). It is shown in [1] that \((T,\sigma)\) is least resolved if and only if it does not contain a redundant edge. Proposition 2 ([1], Thm. 8): _Every BMG \((G,\sigma)\) is explained by a unique least resolved tree (LRT), which is obtained from an arbitrary tree \((T,\sigma)\) that explains \((G,\sigma)\) by contraction of all redundant edges of \((T,\sigma)\)._  
In particular, therefore, there is a bijection between BMGs and LRTs. Surprisingly, the property of being least resolved for some BMG is preserved under contraction of inner edges of \(T\). Theorem 3.1: _Suppose \((T,\sigma)\) is _least resolved and let \(A\) be a set of inner edges of \(T\), and denote by \(T_{A}\) the tree obtained from a tree \(T\) by contracting all edges in \(A\). Then, \((T_{A},\sigma)\) is again _least resolved_. Proof: Assume that \((T,\sigma)\) is least resolved, i.e., it does not contain any redundant edges, and set \((G,\sigma)\coloneqq G(T,\sigma)\). Lemma 7 in [16] states that an inner edge \(e=uv\) with \(v\prec_{T}u\) in \((T,\sigma)\) is non-redundant if and only if there is an arc \((a,b)\in E(G)\) such that \(\operatorname{lca}_{T}(a,b)=v\) and \(\sigma(b)\in\sigma(L(T(u))\setminus L(T(v)))\). The statement trivially holds if \((T,\sigma)\) has at most one inner edge. Therefore, we assume that \((T,\sigma)\) has at least two distinct inner edges \(e=uv\) and \(e^{\prime}\). We show that every non-redundant edge \(e\) in \(T\) remains non-redundant in \(T_{\sigma}\). Thus, let \(e\) be a non-redundant edge in \(T\). Therefore, there is an arc \((a,b)\in E(G)\) such that \(\operatorname{lca}_{T}(a,b)=v\) and \(\sigma(b)\in\sigma(L(T(u))\setminus L(T(v)))\). Now consider the tree \(T_{\sigma^{\prime}}\) obtained from \(T\) by contraction of the inner edge \(e^{\prime}\
eq e\). Clearly, we also have \(\operatorname{lca}_{T_{\sigma}}(a,b)=v\) and \(\sigma(b)\in\sigma(L(T_{\sigma^{\prime}}(u))\setminus L(T_{\sigma^{\prime}}(v)))\). Proposition 1 implies \(G(T,\sigma)\subseteq G(T_{\sigma^{\prime}},\sigma)\), and thus \((a,b)\in E(G(T_{\sigma^{\prime}},\sigma))\).