# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 5 Completion of a 2-BMG to a 2-beBMG
These vertices \(u\) for which \(T(u)\) is replaced by a star are found by a top-down traversal of \(T\) and evaluating \(|\sigma(S_{u})|\), all of which can be computed in linear total time. As an immediate consequence of the uniqueness of \(T^{*}\) and the construction in the second part of the proof of Lemma 3, we obtain the following. Corollary 4: _The collapsed tree \((T^{**},\sigma)\) of a collapsed tree \((T^{*},\sigma)\) satisfies \(T^{**}=T^{*}\)._  
Lemma 4: _If \((T^{*},\sigma)\) is the collapsed tree of an LRT \((T,\sigma)\) with 2-colored leaf set, then \(G(T^{*},\sigma)\) is binary-explainable._  
Proof. : As the collapsed tree \((T^{*},\sigma)\) is obtained from the LRT \((T,\sigma)\) by contraction of edges, Theorem 1 implies that \((T^{*},\sigma)\) is also least resolved. Now suppose, for contradiction, that \(G(T^{*},\sigma)\) is not binary-explainable. By, Proposition 3(3), \((T^{*},\sigma)\) has a vertex \(u\in V^{0}(T^{*})\) with three distinct children--\(v_{1}\), \(v_{2}\), and \(v_{3}\)--and two distinct colors--\(r\) and \(s\)--satisfying (i) \(r\in\sigma(L(T^{*}(v_{1})))\), \(r,s\in\sigma(L(T^{*}(v_{2})))\), and \(s\in\sigma(L(T^{*}(v_{3})))\), and (ii) \(s\
otin\sigma(L(T^{*}(v_{1})))\) and \(r\
otin\sigma(L(T^{*}(v_{3})))\). As \((G,\sigma)\) is only 2-colored, the latter arguments imply that \(|\sigma(L(T^{*}(v_{1})))|=|\sigma(L(T^{*}(v_{3})))|=1\) and \(|\sigma(L(T^{*}(v_{2}))|=2\). As moreover \((T^{*},\sigma)\) is least resolved and none of the vertices \(v_{1}\), \(v_{2}\), and \(v_{3}\) is the root of \(T^{*}\), we can apply Corollary 1 in [20] to conclude that \(v_{1}\) and \(v_{2}\) are leaves, and that \(v_{3}\) is an inner vertex, respectively. In particular, \(\sigma(v_{1})=r\
eq s=\sigma(v_{3})\). Therefore, \(T^{*}(u)\) is not a star tree and \(u\) has support leaves of both colors in \(T^{*}\); a contradiction to its construction. Therefore, we conclude that \(G(T^{*},\sigma)\) is binary-explainable. Theorem 2: _The optimization version of 2-BMG CBEG with a 2-BMG \((G,\sigma)\) as input has the unique solution \(F:=E(G(T^{*},\sigma))\setminus E(G)\), where \((T^{*},\sigma)\) is the collapsed tree of the LRT \((T,\sigma)\) of \((G,\sigma)\)._  
Proof. : First note that the optimization version of 2-BMG CBEG always has a solution. To see this, consider the complete bipartite and properly 2-colored digraph \((G^{\prime},\sigma)\) with vertex set \(V(G)\). This digraph is explained by the star tree with leaf set \(V(G)\). Moreover, \((G^{\prime},\sigma)\) is clearly hourglass-free as hourglasses require non-arcs (between vertices of distinct colors). By Proposition 3, the BMG \((G^{\prime},\sigma)\) is binary-explainable. Now, consider the collapsed tree \((T^{*},\sigma)\) of \((T,\sigma)\). As \(T^{*}\) is obtained from \(T\) by contraction of inner edges, Proposition 1 implies \((G,\sigma)=G(T,\sigma)\subseteq G(T^{*},\sigma)\eqeqcolon(G^{*},\sigma)\). Furthermore, \((G^{*},\sigma)\) is binary-explainable by Lemma 4. Therefore, \((G^{*},\sigma)\) is a valid completion of \((G,\sigma)\) to a beBMG. We continue by showing the existence of certain arcs in every (not necessarily optimal) completion \((G^{\prime},\sigma)\) of \((G,\sigma)\) to a beBMG. To this end, consider a \(\preceq_{T}\)-maximal vertex \(u\) such that the subtree \(T(u)\) is not a star tree and \(u\) has support leaves \(S_{u}\) of both colors in \(T\). We will make frequent use of the fact that \(E(G)\subseteq E(G^{\prime})\). We consider the following cases in order to show that all arcs between vertices \(x,y\in L(T(u))\) with \(\sigma(x)\
eq\sigma(y)\) exist in \((G^{\prime},\sigma)\):  
(i) \(x,y\in S_{u}\),  
(ii) \(x\in L(T(u))\setminus S_{u}\) and \(y\in S_{u}\), and  
(iii) \(x,y\in L(T(u))\setminus S_{u}\). In Case (i), the leaves \(x\) and \(y\) are both children of \(u\). Together with Corollary 3, this implies \((x,y)\), \((y,x)\in E(G)\subseteq E(G^{\prime})\). In Case (ii), we can find a vertex \(x^{\prime}\in S_{u}\) of color \(\sigma(x)\) as \(S_{u}\) contains vertices of both colors.