# 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
Making use of the characterization of redundant edges in ([16], Lemma 7) again, we conclude that \(e\) is non-redundant in \((T_{\sigma^{\prime}},\sigma)\). As both \(e\) and \(e^{\prime}\) were chosen arbitrarily, we observe that the contraction of a single inner edge does not produce new redundant edges. We can therefore apply this argument for each step in the consecutive contraction of all edges in \(A\) (in an arbitrary order) to conclude that \((T_{A},\sigma)\) does not contain redundant edges. Therefore, Proposition 2 implies that \((T_{A},\sigma)\) is least resolved. Corollary 1: _If \((T,\sigma)\) is least resolved and \(A\) is a non-empty set of inner edges of \(T\), then \(G(T,\sigma)\subsetneq G(T_{A},\sigma)\)._  
Proof: By Proposition 1, we have \(G(T,\sigma)\subseteq G(T_{A},\sigma)\). By Theorem 1, \((T_{A},\sigma)\) is least resolved. As the LRT of a BMG is unique (cf. Proposition 2), we have \(G(T,\sigma)\
eq G(T_{A},\sigma)\). As another immediate consequence of Theorem 1 and uniqueness of the LRT of a BMG (Proposition 2), we obtain the following. Corollary 2: _If \(e\) and \(e^{\prime}\) are two distinct inner edges of a least resolved tree \((T,\sigma)\), then \(G(T_{e},\sigma)\
eq G(T_{e^{\prime}},\sigma)\)._  
Let us now turn to the subclass of BMGs that can be explained by a binary tree. Definition 4: _A binary-explainable BMG (beBMG) is a BMG \((G,\sigma)\) such that there is a binary leaf-colored tree \((T,\sigma)\) that explains \((G,\sigma)\)._  
As shown in [16], beBMGs can be characterized among BMGs by means of a simple forbidden colored induced subgraph:  
Definition 5: An _hourglass_ in a properly vertex-colored digraph \((G,\sigma)\), denoted by \([xy\mathrel{\mathop{\kern 0.0 pt\succ}\limits_{\raise 1.29 pt\hbox{$>$}}}x^{ \prime}y^{\prime}]\), is a subgraph \((G[Q],\sigma_{|Q})\) induced by a set of four pairwise distinct vertices \(Q=\{x,x^{\prime},y,y^{\prime}\}\subseteq V(G)\) such that (i) \(\sigma(x)=\sigma(x^{\prime})\
eq\sigma(y)=\sigma(y^{\prime})\), (ii) \((x,y),(y,x)\) and \((x^{\prime}y^{\prime}),(y^{\prime},x^{\prime})\) are bidirectional arcs in \(G\), (iii) \((x,y^{\prime}),(y,x^{\prime})\in E(G)\), and (iv) \((y^{\prime},x),(x^{\prime},y)\
otin E(G)\). An hourglass together with a (non-binary) tree explaining it is illustrated in Figure 1A. A properly vertex-colored digraph that does not contain an hourglass as an induced subgraph is called _hourglass-free_. Proposition 3 ([16], Lemma 31 and Prop. 8): _For every BMG \((G,\sigma)\) explained by a tree \((T,\sigma)\), the following three statements are equivalent:  
Figure 1: (**A**) An hourglass as the characteristic forbidden induced subgraph of beBMGs and its non-binary explaining tree. (**B**) The three classes of forbidden induced subgraphs of 2-colored BMGs (see Definition 6 below). The gray-dashed arcs may or may not exist. \((G,\sigma)\) is binary-explainable. 2. \((G,\sigma)\) is hourglass-free. 3. There is no 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 1. \(r\in\sigma(L(T(v_{1})))\), \(r,s\in\sigma(L(T(v_{2})))\), and \(s\in\sigma(L(T(v_{3})))\), and 2. \(s\
otin\sigma(L(T(v_{1})))\), and \(r\
otin\sigma(L(T(v_{3})))\). Note that the LRTs of beBMGs are usually not binary. In fact, it is shown in [15] that, for a beBMG \((G,\sigma)\), there exists a unique _binary refinable tree_ (BTR) \(B(G,\sigma)\) with the property that every binary tree \((T,\sigma)\) that displays \(B(G,\sigma)\) explains \((G,\sigma)\). The BRT is in general much better resolved than the LRT of \((G,\sigma)\).