# Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs
## 4 Two-Colored BMGs  
Let us now briefly focus on 2-colored BMGs (2-BMGs). As arcs in BMG can only connect vertices with different colors, every 2-BMG is bipartite. Furthermore, every leaf \(x\) in a tree with two leaf colors has at least one best match \(y\). Every 2-BMG is therefore _sink-free_, i.e., every vertex has at least one out-neighbor. Furthermore, [PERSON] et al. [10] showed that the following graphs (see also Figure 1B) are forbidden induced subgraphs for 2-BMGs.  
**Definition 6** (F1-, F2-, and F3-graphs).:
1. _A properly 2-colored digraph on four distinct vertices_ \(V=\{x_{1},x_{2},y_{1},y_{2}\}\) _with coloring_ \(\sigma(x_{1})=\sigma(x_{2})\
eq\sigma(y_{1})=\sigma(y_{2})\) _is an F1-graph if_ \((x_{1},y_{1}),(y_{2},x_{2}),(y_{1},x_{2})\in E\) _and_ \((x_{1},y_{2}),(y_{2},x_{1})\
otin E\)_._
2. _A properly 2-colored digraph on four distinct vertices_ \(V=\{x_{1},x_{2},y_{1},y_{2}\}\) _with coloring_ \(\sigma(x_{1})=\sigma(x_{2})\
eq\sigma(y_{1})=\sigma(y_{2})\) _is an F2-graph if_ \((x_{1},y_{1}),(y_{1},x_{2}),(x_{2},y_{2})\in E\) _and_ \((x_{1},y_{2})\
otin E\)_._
3. _A properly 2-colored digraph on five distinct vertices_ \(V=\{x_{1},x_{2},y_{1},y_{2},y_{3}\}\) _with coloring_ \(\sigma(x_{1})=\sigma(x_{2})\
eq\sigma(y_{1})=\sigma(y_{2})=\sigma(y_{3})\) _is an F3-graph if_ \((x_{1},y_{1}),(x_{2},y_{2}),(x_{1},y_{3}),(x_{2},y_{3})\in E\) _and_ \((x_{1},y_{2}),(x_{2},y_{1})\
otin E\)_._  
**Proposition 4** ([10], Thm. 4.4).: _A properly 2-colored digraph is a BMG if and only if it is sink-free and does not contain an induced F1-, F2-, or F3-graph._  
A peculiar property of 2-BMGs is that their LRTs can be constructed efficiently by recursively decomposing an input 2-BMG into non-trivial induced subgraphs and individual vertices [15]. Although we will not need this construction here, one of its corner stones plays an important role:  
**Definition 7** (Support Leaves).: _For a given tree \(T\), the set \(S_{u}\coloneqq\mathsf{child}_{T}(u)\cap L(T)\) is the set of all support leaves of vertex \(u\in V(T)\)._  
We note in passing that every inner vertex \(u\) of the LRT of a 2-BMG \((G,\sigma)\), with the possible exception of the root \(\rho\), has a non-empty set of support leaves \(S_{u}\), and \(S_{\rho}\
eq\emptyset\) if and only if \((G,\sigma)\) is connected [20]. In the following, we will make use of a connection between a 2-BMG and its LRT.  
**Lemma 1**.: _Let \((G,\sigma)\) be a 2-BMG, \((T,\sigma)\) its LRT, and \(x,y\in L(T)=V(G)\). Then, \((x,y)\in E(G)\) if and only if \(\sigma(x)\
eq\sigma(y)\) and \(y\in L(T(\mathsf{par}_{T}(x)))\)._  
Proof.: First note that as \((G,\sigma)\) is 2-colored, \((T,\sigma)\) has at least two leaves and \(u\coloneqq\mathsf{par}_{T}(x)\) is always defined. First, assume \(\sigma(x)\
eq\sigma(y)\), and thus \(x\
eq y\), and let \(y\in L(T(u))\). As \(x\) is a child of \(u\), we have \(\operatorname{lcar}_{T}(x,y)=u\). Moreover, as \(u\) is the parent of \(x\), there is no vertex \(y^{\prime}\)of color \(\sigma(y)\) such that \(\operatorname{lca}_{T}(x,y^{\prime})\prec_{T}\operatorname{lca}_{T}(x,y)=u\). Therefore, \(y\) is a best match of \(x\), i.e., \((x,y)\in E(G)\).  
Now suppose, for contraposition, that \(\sigma(x)=\sigma(y)\) or \(y\
otin L(T(u))\). If \(\sigma(x)=\sigma(y)\), then, by definition, \((x,y)\
otin E(G)\). If \(y\
otin L(T(u))\), then \(u\prec_{T}\rho_{T}\). Therefore, we can apply Corollary 1 in [20] to the inner vertex \(u\) to conclude that \(|\sigma(L(T(u)))|>1\), i.e., the subtree \(L(T(u))\) contains both colors. Thus, we can find a vertex \(y^{\prime}\) of color \(\sigma(y)\) such that \(\operatorname{lca}_{T}(x,y^{\prime})\preceq_{T}u\prec_{T}\operatorname{lca}_{T }(x,y)\) which implies that \((x,y)\
otin E(G)\).  
As an immediate consequence, we find the following.  
Corollary 3: _Let \((G,\sigma)\) be a 2-BMG, \((T,\sigma)\) its LRT and \(x,y\in V(G)=L(T)\). Then, \((x,y),(y,x)\)\(\in E(G)\) if and only if \(\sigma(x)\
eq\sigma(y)\) and \(\operatorname{par}_{T}(x)=\operatorname{par}_{T}(y)\)._