Proof. By definition, \(G\) is balanced if and only if \(\mathcal{C}(G)\) is balanced. By Theorem 3, this is equivalent to saying that, for every \(W\subseteq V(G)\), the induced subhypergraph \(\mathcal{C}(G)_W\) admits a proper \(2\)-coloring. It remains only to observe that a proper \(2\)-coloring of \(\mathcal{C}(G)_W\) is exactly a proper \(2\)-coloring of \(W\) with respect to \(G\). ◻

Proof. The ‘only if’ implication follows immediately from Lemma 1. To prove the ‘if’ implication, assume that each subset \(W\subseteq V(G)\) such that \(v\in W\) and \(v'\notin W\) admits a proper \(2\)-coloring with respect to \(G\). We prove that, as a consequence, such a coloring also exists for every subset \(W\subseteq V(G)\) such that \(v\notin W\) or \(v'\in W\). Let \(W\) be such a subset. We consider the three possible cases.

Case : \(v\notin W\) and \(v'\in W\). Let \(W_0=(W-\{v'\})\cup\{v\}\). Since \(v\in W_0\) and \(v'\notin W_0\), our assumption yields a proper \(2\)-coloring \(\phi_0\) of \(W_0\) with respect to \(G\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W-\{v'\}}=\phi_0\vert_{W-\{v'\}}\) and \(\phi(v')=\phi_0(v)\). Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\) contains neither \(v\) nor \(v'\). Thus, \(Q\cap W=Q\cap W_0\) and this set has at least two vertices. Since \(\phi_0\) is proper and \(\phi\) agrees with \(\phi_0\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Suppose now that \(v'\in Q\). Let \(Q_0=(Q-\{v'\})\cup\{v\}\). Since \(v\) and \(v'\) are false twins in \(G\), \(Q_0\) is a maximal clique of \(G\). Since \(Q_0\cap W_0\) is obtained from \(Q\cap W\) by replacing \(v'\) with \(v\), we have \(\vert Q_0\cap W_0\vert=\vert Q\cap W\vert\geq 2\). By the properness of \(\phi_0\), \(Q_0\cap W_0\) is not monochromatic under \(\phi_0\). By the definition of \(\phi\), this implies that \(Q\cap W\) is not monochromatic under \(\phi\). Suppose finally that \(v\in Q\). Let \(Q_0=(Q-\{v\})\cup\{v'\}\). Since \(v\) and \(v'\) are false twins in \(G\), \(Q_0\) is a maximal clique of \(G\) and \(Q_0\cap W_0=Q\cap W\). Hence, by the properness of \(\phi_0\) and since \(\phi\) and \(\phi_0\) agree on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Therefore, \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\).

Case : \(v\in W\) and \(v'\in W\). Let \(W_0=W-\{v'\}\). Since \(v\in W_0\) and \(v'\notin W_0\), our assumption yields a proper \(2\)-coloring \(\phi_0\) of \(W_0\) with respect to \(G\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_0}=\phi_0\) and \(\phi(v')=\phi_0(v)\). Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(v'\notin Q\). Thus, \(Q\cap W=Q\cap W_0\) and this set has at least two vertices. Since \(\phi_0\) is proper and \(\phi\) agrees with \(\phi_0\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Suppose otherwise that \(v'\in Q\) and let \(Q_0=(Q-\{v'\})\cup\{v\}\). Since \(v\) and \(v'\) are false twins in \(G\), \(Q_0\) is a maximal clique of \(G\). Since \(Q_0\cap W_0\) is obtained from \(Q\cap W\) by replacing \(v'\) with \(v\), we have \(\vert Q_0\cap W_0\vert=\vert Q\cap W\vert\geq 2\). By the properness of \(\phi_0\), \(Q_0\cap W_0\) is not monochromatic under \(\phi_0\). Since \(\phi\) agrees with \(\phi_0\) on \((Q\cap W)-\{v'\}\) and \(\phi(v')=\phi_0(v)\), \(Q\cap W\) is not monochromatic under \(\phi\). Therefore, \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\).

Case : \(v\notin W\) and \(v'\notin W\). Let \(W_0=W\cup\{v\}\). Since \(v\in W_0\) and \(v'\notin W_0\), our assumption yields a proper \(2\)-coloring \(\phi_0\) of \(W_0\) with respect to \(G\). Let \(\phi=\phi_0\vert_W\). Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(v\notin Q\). Since \(Q\cap W=Q\cap W_0\) and \(\phi=\phi_0\vert_W\), the properness of \(\phi_0\) implies that \(Q\cap W\) is not monochromatic under \(\phi\). Suppose otherwise that \(v\in Q\) and let \(Q_0=(Q-\{v\})\cup\{v'\}\). Since \(v\) and \(v'\) are false twins in \(G\), \(Q_0\) is a maximal clique of \(G\). Since \(Q_0\cap W_0=Q\cap W\) and \(\phi=\phi_0\vert_W\), the properness of \(\phi_0\) implies that \(Q\cap W\) is not monochromatic under \(\phi\). Therefore, \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\).

As we have proved that every subset \(W\subseteq V(G)\) admits a proper \(2\)-coloring with respect to \(G\), Lemma 1 implies that \(G\) is balanced. This completes the proof of the lemma. ◻

Proof. Let \(G=H_1\ast H_2\) and let \(Q\) be a maximal clique of \(G\).

Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). Since \(G_i\) is an induced subgraph of \(G\), \(Q\) is a maximal clique of \(G_i\). Moreover, \(Q\) is not contained in \(X_i\), since otherwise a vertex of \(X_{3-i}\) would be adjacent in \(G\) to every vertex of \(Q\), contradicting the maximality of \(Q\) in \(G\). Thus, in this case, assertion [it:Q1] holds.

Suppose now that \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). For each \(i\in\{1,2\}\), let \(R_i=Q\cap V(G_i)\). Since \(V(G_1)\) and \(V(G_2)\) partition \(V(G)\), we have \(Q=R_1\cup R_2\), where \(R_1\) and \(R_2\) are both nonempty. Since \(Q\) is a clique of \(G\), \(R_1\) is complete to \(R_2\) in \(G\). By the definition of \(H_1\ast H_2\), this implies that \(R_1\subseteq X_1\) and \(R_2\subseteq X_2\). Since \(G_i\) is an induced subgraph of \(G\), \(R_i\) is a clique of \(G_i[X_i]\) for each \(i\in\{1,2\}\). Finally, for each \(i\in\{1,2\}\), \(R_i\) is a maximal clique of \(G_i[X_i]\), since any vertex of \(X_i-R_i\) complete to \(R_i\) in \(G_i\) would also be complete to \(R_{3-i}\) in \(G\) (as \(X_i\) is complete to \(X_{3-i}\) in \(G\) and \(R_{3-i}\subseteq X_{3-i}\)) and hence complete to \(Q\) in \(G\), contradicting the maximality of \(Q\) in \(G\). Therefore, in this case, assertion [it:Q2] holds. This completes the proof of the lemma. ◻

Proof. Throughout this proof, let \(G=H_1\ast H_2\), let \(G_i=H_i-v\) for each \(i\in\{1,2\}\), and let \(v'\) denote, for each \(i\in\{1,2\}\), the false twin of \(v\) in \(H_i^+\).

Suppose that \(G\) is balanced. Since \(X_1\) and \(X_2\) are nonempty, let \(x_i\) be a vertex of \(X_{3-i}\) for each \(i\in\{1,2\}\). For each \(i\in\{1,2\}\), \(H_i\) is isomorphic to \(G[V(G_i)\cup\{x_i\}]\), which is balanced as an induced subgraph of the balanced graph \(G\). We now show that, for each \(i\in\{1,2\}\), if \(X_{3-i}\) is not a clique of \(H_{3-i}\), then \(H_i^+\) is balanced. Let \(i\in\{1,2\}\) and suppose that \(X_{3-i}\) is not a clique of \(H_{3-i}\). Let \(y\) and \(y'\) be two vertices of \(X_{3-i}\) that are nonadjacent in \(H_{3-i}\). The graph \(H_i^+\) is isomorphic to \(G[V(G_i)\cup\{y,y'\}]\), which is balanced as an induced subgraph of the balanced graph \(G\). Hence, \(H_i^+\) is balanced. Thus, the ‘only if’ implications in assertions [item:TSareCliques], [item:TS1isClique], and [item:TSareNotCliques] hold. It only remains to prove the ‘if’ implication in each assertion.

For each of the three ‘if’ implications below, let \(W\) be an arbitrary subset of \(V(G)\). By Lemma 1, to prove that \(G\) is balanced under the hypotheses of the corresponding assertion, it suffices to give a proper \(2\)-coloring of \(W\) with respect to \(G\).

Proof of the ‘if’ implication in assertion [item:TSareCliques]. Suppose that \(X_1\) is a clique of \(H_1\) and \(X_2\) is a clique of \(H_2\). Suppose, in addition, that \(H_1\) and \(H_2\) are balanced. For each \(i\in\{1,2\}\), let \(W_i=W\cap V(G_i)\) if \(W\cap X_{3-i}=\emptyset\) and let \(W_i=(W\cap V(G_i))\cup\{v\}\) otherwise. Since \(H_i\) is balanced for each \(i\in\{1,2\}\), Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i\). If \(v\in W_1\cap W_2\), interchange the colors of \(\phi_2\) if necessary so that \(\phi_1(v)\neq\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W\cap V(G_i)}=\phi_i\vert_{W\cap V(G_i)}\) for each \(i\in\{1,2\}\). This is well defined because \(V(G_1)\) and \(V(G_2)\) partition \(V(G)\).

Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). Since \(X_1\) is a clique of \(G_1\) and \(X_2\) is a clique of \(G_2\), Lemma 3 implies that one of the following two cases holds for \(Q\).

Case : \(Q\) is a maximal clique of \(G_i\) not contained in \(X_i\), for some \(i\in\{1,2\}\). Hence, \(Q\cup\{v\}\) is not a clique of \(H_i\). Therefore, \(Q\) is a maximal clique of \(H_i\) and \(Q\cap W=Q\cap W_i\). The properness of \(\phi_i\) implies that \(Q\cap W_i\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(Q\cap W_i\), \(Q\cap W\) is not monochromatic under \(\phi\).

Case : \(Q=X_1\cup X_2\). Hence, \(X_i\cup\{v\}\) is a maximal clique of \(H_i\) for each \(i\in\{1,2\}\), because \(N_{H_i}(v)=X_i\). We consider the following two subcases.

Subcase .: \(W\cap X_1=\emptyset\) or \(W\cap X_2=\emptyset\). Let \(i\in\{1,2\}\) be such that \(W\cap X_{3-i}=\emptyset\). Since \(Q=X_1\cup X_2\) and \(\vert Q\cap W\vert\geq 2\), we have \(Q\cap W=X_i\cap W\) and \(\vert X_i\cap W\vert\geq 2\). By the definition, \(W_i=W\cap V(G_i)\). Thus, \((X_i\cup\{v\})\cap W_i=X_i\cap W\). Since \(X_i\cup\{v\}\) is a maximal clique of \(H_i\), the properness of \(\phi_i\) implies that \(X_i\cap W\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(X_i\cap W\), the equality \(Q\cap W=X_i\cap W\) implies that \(Q\cap W\) is not monochromatic under \(\phi\).

Subcase .: \(W\cap X_1\neq\emptyset\) and \(W\cap X_2\neq\emptyset\). By definition, \(v\in W_i\) for each \(i\in\{1,2\}\). Hence, \((X_i\cup\{v\})\cap W_i\) has at least two vertices for each \(i\in\{1,2\}\). Since \(X_i\cup\{v\}\) is a maximal clique of \(H_i\), the properness of \(\phi_i\) ensures the existence of a vertex \(x_i\in X_i\cap W\) such that \(\phi_i(x_i)\neq\phi_i(v)\) for each \(i\in\{1,2\}\). Since there are only two colors and \(\phi_1(v)\neq\phi_2(v)\), it follows that \(\phi(x_1)\neq\phi(x_2)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\).

The two cases for \(Q\) above exhaust all possibilities and in each case \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\). Since \(W\) is an arbitrary subset of \(V(G)\), Lemma 1 implies that \(G\) is balanced. This completes the proof of the ‘if’ implication of assertion [item:TSareCliques].

Proof of the ‘if’ implication in assertion [item:TS1isClique]. Suppose that \(X_1\) is a clique of \(H_1\) and \(X_2\) is not a clique of \(H_2\). Suppose, in addition, that \(H_1^+\) and \(H_2\) are balanced. Let \(W_1=(W\cap V(G_1))\cup\{v\}\). Let \(W_2=W\cap V(G_2)\) if \(W\cap X_1=\emptyset\) and let \(W_2=(W\cap V(G_2))\cup\{v\}\) otherwise. Since \(H_1^+\) and \(H_2\) are balanced, Lemma 1 yields a proper \(2\)-coloring \(\phi_1\) of \(W_1\) with respect to \(H_1^+\) and a proper \(2\)-coloring \(\phi_2\) of \(W_2\) with respect to \(H_2\). If \(v\in W_2\), interchange the colors of \(\phi_2\) if necessary so that \(\phi_1(v)\neq\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W\cap V(G_i)}=\phi_i\vert_{W\cap V(G_i)}\) for each \(i\in\{1,2\}\).

Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). Since \(X_1\) is a clique of \(G_1\), Lemma 3 implies that one of the following two cases holds for \(Q\).

Case : \(Q\) is a maximal clique of \(G_i\) not contained in \(X_i\), for some \(i\in\{1,2\}\). If \(i=1\), then neither \(Q\cup\{v\}\) nor \(Q\cup\{v'\}\) is a clique of \(H_1^+\). Hence, \(Q\) is a maximal clique of \(H_1^+\). If \(i=2\), then \(Q\cup\{v\}\) is not a clique of \(H_2\). Hence, \(Q\) is a maximal clique of \(H_2\). In either case, \(Q\cap W=Q\cap W_i\). The properness of \(\phi_i\) implies that \(Q\cap W_i\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(Q\cap W_i\), \(Q\cap W\) is not monochromatic under \(\phi\).

Case : \(Q=X_1\cup R_2\), where \(R_2\) is a maximal clique of \(G_2[X_2]\). Since \(X_1\) is a clique of \(H_1\), \(X_1\cup\{v\}\) and \(X_1\cup\{v'\}\) are maximal cliques of \(H_1^+\), because each of \(v\) and \(v'\) is adjacent exactly to \(X_1\) in \(H_1^+\) and \(v\) and \(v'\) are nonadjacent in \(H_1^+\). Also, \(R_2\cup\{v\}\) is a maximal clique of \(H_2\), since any vertex of \(H_2\) complete to \(R_2\cup\{v\}\) would belong to \(X_2-R_2\), contradicting the maximality of \(R_2\) in \(G_2[X_2]\). We now consider subcases according to the size of \(X_1\cap W\).

Subcase .: \(\vert X_1\cap W\vert\geq 2\). Since \((X_1\cup\{v'\})\cap W_1=X_1\cap W\) and \(X_1\cup\{v'\}\) is a maximal clique of \(H_1^+\), the properness of \(\phi_1\) implies that \(X_1\cap W\) is not monochromatic under \(\phi_1\). Since \(X_1\cap W\subseteq Q\cap W\) and \(\phi\) agrees with \(\phi_1\) on \(X_1\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\).

Subcase .: \(\vert X_1\cap W\vert=1\). Let \(x_1\) be the unique vertex of \(X_1\cap W\). Since \((X_1\cup\{v\})\cap W_1=\{x_1,v\}\), the properness of \(\phi_1\) implies \(\phi_1(x_1)\neq\phi_1(v)\). Since \(Q=X_1\cup R_2\), the assumptions \(\vert X_1\cap W\vert=1\) and \(\vert Q\cap W\vert\geq 2\) imply that \(R_2\cap W\) is nonempty. Moreover, since \(W\cap X_1\) is nonempty, we have \(v\in W_2\). Thus, the maximal clique \(R_2\cup\{v\}\) of \(H_2\) has at least two vertices in \(W_2\). Hence, the properness of \(\phi_2\) ensures the existence of a vertex \(x_2\in R_2\cap W\) such that \(\phi_2(x_2)\neq\phi_2(v)\). Since there are only two colors and \(\phi_1(v)\neq\phi_2(v)\), it follows that \(\phi(x_1)\neq\phi(x_2)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\).

Subcase .: \(X_1\cap W=\emptyset\). In this subcase, \(W_2=W\cap V(G_2)\) and \(Q\cap W=R_2\cap W\). Since \(\vert Q\cap W\vert\geq 2\), the maximal clique \(R_2\cup\{v\}\) of \(H_2\) has at least two vertices in \(W_2\). The properness of \(\phi_2\) implies that \(Q\cap W\) is not monochromatic under \(\phi\).

The two cases for \(Q\) above exhaust all possibilities and in each case \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\). Since \(W\) is an arbitrary subset of \(V(G)\), Lemma 1 implies that \(G\) is balanced. This completes the proof of the ‘if’ implication of assertion [item:TS1isClique].

Proof of the ‘if’ implication in assertion [item:TSareNotCliques]. Suppose that neither \(X_1\) is a clique of \(H_1\) nor \(X_2\) is a clique of \(H_2\). Suppose, in addition, that \(H_1^+\) and \(H_2^+\) are balanced. For each \(i\in\{1,2\}\), let \(W_i=(W\cap V(G_i))\cup\{v\}\). Since \(H_i^+\) is balanced for each \(i\in\{1,2\}\), Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i^+\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_1(v)\neq\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W\cap V(G_i)}=\phi_i\vert_{W\cap V(G_i)}\) for each \(i\in\{1,2\}\).

Let \(Q\) be a maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\). By Lemma 3, one of the following two cases holds for \(Q\).

Case : \(Q\) is a maximal clique of \(G_i\) not contained in \(X_i\), for some \(i\in\{1,2\}\). Hence, neither \(Q\cup\{v\}\) nor \(Q\cup\{v'\}\) is a clique of \(H_i^+\). Therefore, \(Q\) is a maximal clique of \(H_i^+\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W_i\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(Q\cap W_i\), \(Q\cap W\) is not monochromatic under \(\phi\).

Case : \(Q=R_1\cup R_2\), where \(R_i\) is a maximal clique of \(G_i[X_i]\) for each \(i\in\{1,2\}\). We consider two subcases according to the sizes of \(R_1\cap W\) and \(R_2\cap W\).

Subcase .: \(\vert R_i\cap W\vert\geq 2\) for some \(i\in\{1,2\}\). The set \(R_i\cup\{v'\}\) is a maximal clique of \(H_i^+\), since any vertex of \(H_i^+\) complete to \(R_i\cup\{v'\}\) would belong to \(X_i-R_i\), contradicting the maximality of \(R_i\) in \(G_i[X_i]\). Since \((R_i\cup\{v'\})\cap W_i=R_i\cap W\), the properness of \(\phi_i\) implies that \(R_i\cap W\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(R_i\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\).

Subcase .: \(\vert R_i\cap W\vert\leq 1\) for each \(i\in\{1,2\}\). Since \(Q\cap W=(R_1\cap W)\cup(R_2\cap W)\) and \(\vert Q\cap W\vert\geq 2\), both \(R_1\cap W\) and \(R_2\cap W\) have exactly one vertex. Let \(x_i\) be the unique vertex of \(R_i\cap W\) for each \(i\in\{1,2\}\). For each \(i\in\{1,2\}\), the set \(R_i\cup\{v\}\) is a maximal clique of \(H_i^+\), since any vertex of \(H_i^+\) complete to \(R_i\cup\{v\}\) would belong to \(X_i-R_i\), contradicting the maximality of \(R_i\) in \(G_i[X_i]\). Since \((R_i\cup\{v\})\cap W_i=\{x_i,v\}\), the properness of \(\phi_i\) implies \(\phi_i(x_i)\neq\phi_i(v)\) for each \(i\in\{1,2\}\). Since there are only two colors and \(\phi_1(v)\neq\phi_2(v)\), it follows that \(\phi(x_1)\neq\phi(x_2)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\).

The two cases for \(Q\) above exhaust all possibilities and in each case \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(G\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(G\). Since \(W\) is an arbitrary subset of \(V(G)\), Lemma 1 implies that \(G\) is balanced. This completes the proof of the ‘if’ implication of assertion [item:TSareNotCliques] and thus the proof of the proposition. ◻

Proof. Let \(T\) be an \(\mathop{\mathrm{OVE}}\)-tree and let \(G\), \(H\), and \(H^+\) be as in the statement. We prove by induction on the definition of \(\mathop{\mathrm{OVE}}\)-trees that if \(G\) is balanced, then both assertions [item:2vertices] and [item:1vertex] hold. The two assertions are proved simultaneously: in the inductive step, assertion [item:2vertices] for \(T=T_1\oplus_\alpha T_2\) is proved using assertion [item:2vertices] for \(T_1\) and \(T_2\), while assertion [item:1vertex] for \(T\) is proved using, as needed, assertions [item:2vertices] and [item:1vertex] for \(T_1\) and \(T_2\), and assertion [item:2vertices] already proved for the same tree \(T\).

If \(T\) has exactly one vertex, then \(G=K_1\), \(H=K_2\), and \(H^+=P_3\). As \(H\) and \(H^+\) are balanced, both assertions [item:2vertices] and [item:1vertex] hold.

For the rest of the proof, suppose that \(T=T_1\oplus_\alpha T_2\) with \(\alpha\in\{\mathsf{f},\mathsf{t},\mathsf{p}\}\) and that \(G\) is balanced. For each \(i\in\{1,2\}\), let \(G_i=\mathop{\mathrm{DH}}(T_i)\) and let \(X_i=\mathop{\mathrm{TS}}(T_i)\). For each \(i\in\{1,2\}\), let \(H_i\) be the graph that arises from \(G_i\) by adding a vertex \(v\) such that \(N_{H_i}(v)=X_i\) and let \(H_i^+\) be the graph that arises from \(H_i\) by adding a false twin \(v'\) of \(v\). By Remark 5, for each \(i\in\{1,2\}\), \(G_i=G[V(T_i)]\) and thus \(G_i\) is balanced as an induced subgraph of the balanced graph \(G\). By the induction hypothesis, for each \(i\in\{1,2\}\), both assertions [item:2vertices] and [item:1vertex] hold for \(T_i\). Notice that, if \(\alpha\in\{\mathsf{t},\mathsf{p}\}\), then, by Definition 2, \(G=H_1\ast H_2\).

Proof of assertion [item:2vertices]. Assume that no induced \(\overline{3K_2}\) of \(H^+\) contains both \(v\) and \(v'\). We will prove that \(H^+\) is balanced. By Lemma 2, it suffices to show that every subset \(W\) of \(V(H^+)\) such that \(v\in W\) and \(v'\notin W\) admits a proper \(2\)-coloring with respect to \(H^+\). Let \(W\) be such a subset. For each \(i\in\{1,2\}\), let \(W_i=W\cap V(H_i)\). Since \(v\in W\), for each \(i\in\{1,2\}\), we have \(W_i=(W\cap V(G_i))\cup\{v\}\). Since \(v'\notin W\), we also have \(W_i=W\cap V(H_i^+)\) for each \(i\in\{1,2\}\). In the cases and subcases below, we will define \(\phi\) by prescribing its values either on \(W_1\) and \(W_2-\{v\}\), or on \(W_1-\{v\}\) and \(W_2\). Since \(W_1\cup W_2=W\) and \(W_1\cap W_2=\{v\}\), each such \(2\)-coloring \(\phi\) will be well defined.

We first prove a claim that will be used in the case analysis.

Claim : For every \(i\in\{1,2\}\), except possibly when both \(\alpha=\mathsf{p}\) and \(i=2\), \(H_i^+\) is balanced. Let \(i\in\{1,2\}\) and suppose that \((\alpha,i)\neq(\mathsf{p},2)\). Thus, by Definition 2, we have \(H_i^+=H^+[V(G_i)\cup\{v,v'\}]\). Since \(H_i^+\) is an induced subgraph of \(H^+\), the assumption on \(H^+\) implies that no induced \(\overline{3K_2}\) of \(H_i^+\) contains both \(v\) and \(v'\). Hence, by assertion [item:2vertices] for \(T_i\), \(H_i^+\) is balanced.

We first consider three cases according to the value of \(\alpha\).

Case : \(\alpha=\mathsf{f}\). By Claim [claim:Hi43-balanced], \(H_i^+\) is balanced for each \(i\in\{1,2\}\). Hence, Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i^+\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_1(v)=\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\phi_2\vert_{W_2-\{v\}}\). Since \(\phi_1(v)=\phi_2(v)\), \(\phi\) agrees with \(\phi_i\) on \(W_i\) for each \(i\in\{1,2\}\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). In this case, there are no edges of \(H^+\) with one endpoint in \(V(G_1)\) and the other in \(V(G_2)\). Hence, \(Q\subseteq V(H_i^+)\) for some \(i\in\{1,2\}\). As \(H_i^+\) is an induced subgraph of \(H^+\), \(Q\) is maximal in \(H_i^+\). Since \(Q\cap W=Q\cap W_i\) and \(\vert Q\cap W\vert\geq 2\), the properness of \(\phi_i\) implies that \(Q\cap W_i\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(W_i\), \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Case : \(\alpha=\mathsf{t}\). By Claim [claim:Hi43-balanced], \(H_i^+\) is balanced for each \(i\in\{1,2\}\). Hence, Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i^+\).

We first show that \(X_1\) is a clique of \(G_1\) or \(X_2\) is a clique of \(G_2\). Suppose, for a contradiction, that neither \(X_1\) is a clique of \(G_1\) nor \(X_2\) is a clique of \(G_2\). Let \(x_1\) and \(y_1\) be two vertices of \(X_1\) that are nonadjacent in \(G_1\) and let \(x_2\) and \(y_2\) be two vertices of \(X_2\) that are nonadjacent in \(G_2\). Since \(\alpha=\mathsf{t}\), \(X_1\) is complete to \(X_2\) in \(G\). Therefore, \(\{x_1,y_1,x_2,y_2,v,v'\}\) induces \(\overline{3K_2}\) in \(H^+\). This contradicts the assumption that no induced \(\overline{3K_2}\) of \(H^+\) contains both \(v\) and \(v'\).

By symmetry, suppose that \(X_1\) is a clique of \(G_1\). Hence, \(X_1\cup\{v\}\) and \(X_1\cup\{v'\}\) are maximal cliques of \(H_1^+\), because each of \(v\) and \(v'\) is adjacent exactly to \(X_1\) in \(H_1^+\) and \(v\) and \(v'\) are nonadjacent in \(H_1^+\).

We next prove a claim about maximal cliques contained in neither \(V(G_1)\) nor \(V(G_2)\) that will be used in the subcases below.

Claim : If \(Q\) is a maximal clique of \(H^+\) contained in neither \(V(G_1)\) nor \(V(G_2)\), then \(Q=X_1\cup R_2\cup\{u\}\), where \(R_2\) is a maximal clique of \(G_2[X_2]\) and \(u\in\{v,v'\}\). In particular, \(Q-X_1\) equals \(R_2\cup\{u\}\), which is a maximal clique of \(H_2^+\). Let \(Q\) be a maximal clique of \(H^+\) contained in neither \(V(G_1)\) nor \(V(G_2)\). Since \(v\) and \(v'\) are nonadjacent in \(H^+\), \(Q\) contains at most one of them. We first show that \(Q\) contains one of them. Suppose otherwise. Thus, \(Q\subseteq V(G)\) and, since \(G\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(G\). Since \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\), Lemma 3 implies that \(Q\subseteq X_1\cup X_2\). Hence, \(Q\cup\{v\}\) is a clique of \(H^+\), contradicting the maximality of \(Q\) in \(H^+\). Thus, \(Q\) contains exactly one of \(v\) and \(v'\). Let \(u\) be this vertex. Moreover, \((Q-\{u\})\cap V(G_i)\neq\emptyset\) for each \(i\in\{1,2\}\). Indeed, if \((Q-\{u\})\cap V(G_i)=\emptyset\) for some \(i\in\{1,2\}\), then \(Q-\{u\}\subseteq X_{3-i}\) and hence any vertex of \(X_i\) would be complete to \(Q\) in \(H^+\), contradicting the maximality of \(Q\) in \(H^+\). Therefore, \(Q-\{u\}\) is a maximal clique of \(G\), since any vertex of \(G\) complete to \(Q-\{u\}\) in \(G\) would have to lie in \(X_1\cup X_2\) (because \(Q-\{u\}\) meets both \(V(G_1)\) and \(V(G_2)\)) and would also be adjacent to \(u\) in \(H^+\), contradicting the maximality of \(Q\) in \(H^+\). Since \(Q-\{u\}\) is contained in neither \(V(G_1)\) nor \(V(G_2)\) and \(X_1\) is a clique of \(G_1\), Lemma 3 implies that \(Q-\{u\}=X_1\cup R_2\), where \(R_2\) is a maximal clique of \(G_2[X_2]\). Hence, \(Q=X_1\cup R_2\cup\{u\}\). Finally, \(Q-X_1\) equals \(R_2\cup\{u\}\), which is a maximal clique of \(H_2^+\) because \(N_{H_2^+}(u)=X_2\). This proves the claim.

We now consider three subcases according to the size of \(X_1\cap W\).

Subcase .: \(\vert X_1\cap W\vert\geq 2\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\phi_2\vert_{W_2-\{v\}}\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). Thus, \(Q\) is a maximal clique of \(H_i^+\), since \(H_i^+=H^+[V(G_i)\cup\{v,v'\}]\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W\) is not monochromatic under \(\phi_i\). As \(\phi\) agrees with \(\phi_i\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). Thus, by Claim [claim:aux-cliques], we have \(X_1\subseteq Q\). Since \(X_1\cup\{v'\}\) is a maximal clique of \(H_1^+\) and \((X_1\cup\{v'\})\cap W_1=X_1\cap W\), the properness of \(\phi_1\) implies that \(X_1\cap W\) is not monochromatic under \(\phi_1\). Since \(X_1\cap W\subseteq Q\cap W\) and \(\phi\) agrees with \(\phi_1\) on \(W_1\), \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcase .: \(\vert X_1\cap W\vert=1\). Let \(w_1\) be the unique vertex of \(X_1\cap W\). Since \(X_1\cup\{v\}\) is a maximal clique of \(H_1^+\), the properness of \(\phi_1\) applied to \((X_1\cup\{v\})\cap W_1=\{w_1,v\}\) implies \(\phi_1(w_1)\neq\phi_1(v)\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_2(v)=\phi_1(w_1)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\phi_2\vert_{W_2-\{v\}}\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). Thus, \(Q\) is a maximal clique of \(H_i^+\), since \(H_i^+=H^+[V(G_i)\cup\{v,v'\}]\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W\) is not monochromatic under \(\phi_i\). As \(\phi\) agrees with \(\phi_i\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). Thus, by Claim [claim:aux-cliques], there exist a maximal clique \(R_2\) of \(G_2[X_2]\) and a vertex \(u\in\{v,v'\}\) such that \(Q=X_1\cup R_2\cup\{u\}\) and \(R_2\cup\{u\}\) is a maximal clique of \(H_2^+\). Since \(X_1\cap W=\{w_1\}\), we have \(w_1\in Q\cap W\). If \(u=v\), then \(\phi(v)=\phi_1(v)\neq\phi_1(w_1)=\phi(w_1)\), so \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(u=v'\). Let \(Q'=R_2\cup\{v\}\). Since \(R_2\cup\{v'\}\) is a maximal clique of \(H_2^+\) and \(v\) and \(v'\) are false twins in \(H_2^+\), \(Q'\) is also a maximal clique of \(H_2^+\). Since \(\vert Q\cap W\vert\geq 2\), \(X_1\cap W=\{w_1\}\), and \(v'\notin W\), \(R_2\cap W\) is nonempty. Since \(v\in W\), we have \(\vert Q'\cap W\vert\geq 2\). Thus, the properness of \(\phi_2\) ensures the existence of a vertex \(w_2\in R_2\cap W\) such that \(\phi_2(w_2)\neq\phi_2(v)\). Hence, \(w_2\in Q\cap W\) and \(\phi(w_2)=\phi_2(w_2)\neq\phi_2(v)=\phi_1(w_1)=\phi(w_1)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcase .: \(X_1\cap W=\emptyset\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1-\{v\}}=\phi_1\vert_{W_1-\{v\}}\) and \(\phi\vert_{W_2}=\phi_2\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). Thus, \(Q\) is a maximal clique of \(H_i^+\), since \(H_i^+=H^+[V(G_i)\cup\{v,v'\}]\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W\) is not monochromatic under \(\phi_i\). As \(\phi\) agrees with \(\phi_i\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). Thus, by Claim [claim:aux-cliques], \(Q-X_1\) is a maximal clique of \(H_2^+\). Since \(X_1\cap W=\emptyset\), we have \(Q\cap W=(Q-X_1)\cap W_2\). Since \(\vert Q\cap W\vert\geq 2\), the properness of \(\phi_2\) implies that \((Q-X_1)\cap W_2\) is not monochromatic under \(\phi_2\). Since \(\phi\) agrees with \(\phi_2\) on \(W_2\), \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

The three subcases above cover all possibilities and, in each of them, \(W\) admits a proper \(2\)-coloring with respect to \(H^+\).

Case : \(\alpha=\mathsf{p}\). By Claim [claim:Hi43-balanced], \(H_1^+\) is balanced. Hence, Lemma 1 yields a proper \(2\)-coloring \(\phi_1\) of \(W_1\) with respect to \(H_1^+\).

We first consider two subcases according to whether or not \(G_2[X_2]\) contains an induced \(C_4\).

Subcase .: \(G_2[X_2]\) contains no induced \(C_4\). Notice that, if some induced \(\overline{3K_2}\) of \(H_2^+\) contained both \(v\) and \(v'\), then the four vertices other than \(v\) and \(v'\) would have to lie in \(X_2\) and would induce a \(C_4\) in \(G_2[X_2]\), a contradiction. Thus, no induced \(\overline{3K_2}\) of \(H_2^+\) contains both \(v\) and \(v'\). By assertion [item:2vertices] for \(T_2\), \(H_2^+\) is balanced. Hence, Lemma 1 yields a proper \(2\)-coloring \(\phi_2\) of \(W_2\) with respect to \(H_2^+\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_1(v)\neq\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\phi_2\vert_{W_2-\{v\}}\).

Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(H_1^+)\). Thus, \(Q\) is a maximal clique of \(H_1^+\), since \(H_1^+\) is an induced subgraph of \(H^+\). Since \(Q\cap W=Q\cap W_1\) and \(\vert Q\cap W\vert\geq 2\), the properness of \(\phi_1\) implies that \(Q\cap W_1\) is not monochromatic under \(\phi_1\). Since \(\phi\) agrees with \(\phi_1\) on \(W_1\), \(Q\cap W\) is not monochromatic under \(\phi\). Suppose now that \(Q\subseteq V(G_2)\). Thus, \(Q\) is a maximal clique of \(G_2\). In fact, \(Q\) is a maximal clique of \(H_2^+\), since otherwise one of \(v\) and \(v'\) would be complete to \(Q\), forcing \(Q\subseteq X_2\) and thus \(Q\cup\{x_1\}\) would be a clique of \(H^+\) for any \(x_1\in X_1\), contradicting the maximality of \(Q\) in \(H^+\). Since \(Q\cap W=Q\cap(W_2-\{v\})\) and \(\vert Q\cap W\vert\geq 2\), the properness of \(\phi_2\) implies that \(Q\cap W\) is not monochromatic under \(\phi_2\). Since \(\phi\) agrees with \(\phi_2\) on \(W_2-\{v\}\), \(Q\cap W\) is not monochromatic under \(\phi\).

It only remains to consider the case where \(Q\) is contained in neither \(V(H_1^+)\) nor \(V(G_2)\). Since \(V(H_1^+)\) and \(V(G_2)\) partition \(V(H^+)\), \(Q\) meets both \(V(H_1^+)\) and \(V(G_2)\). As neither \(v\) nor \(v'\) is adjacent in \(H^+\) to a vertex of \(G_2\), \(Q\) meets both \(V(G_1)\) and \(V(G_2)\). Since \(\alpha=\mathsf{p}\), the only edges of \(H^+\) with one endpoint in \(V(G_1)\) and the other in \(V(G_2)\) have one endpoint in \(X_1\) and the other in \(X_2\). Hence, \(Q\subseteq X_1\cup X_2\). Thus, \(Q\subseteq V(G)\). Since \(G\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(G\). Since \(Q\) meets both \(V(G_1)\) and \(V(G_2)\), Lemma 3 implies that \(Q=R_1\cup R_2\), where \(R_i\) is a maximal clique of \(G_i[X_i]\) for each \(i\in\{1,2\}\). If \(\vert R_i\cap W\vert\geq 2\) for some \(i\in\{1,2\}\), then \(R_i\cup\{v'\}\) is a maximal clique of \(H_i^+\), because \(R_i\) is maximal in \(G_i[X_i]\) and \(v'\) is adjacent exactly to \(X_i\) in \(H_i^+\). Since \((R_i\cup\{v'\})\cap W_i=R_i\cap W\), the properness of \(\phi_i\) implies that \(R_i\cap W\) is not monochromatic under \(\phi_i\). Since \(R_i\cap W\subseteq Q\cap W\) and \(\phi\) agrees with \(\phi_i\) on \(W_i-\{v\}\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(\vert R_i\cap W\vert=1\) for each \(i\in\{1,2\}\). Let \(w_i\) be the unique vertex of \(R_i\cap W\) for each \(i\in\{1,2\}\). Moreover, for each \(i\in\{1,2\}\), \(R_i\cup\{v\}\) is a maximal clique of \(H_i^+\) and \((R_i\cup\{v\})\cap W_i=\{v,w_i\}\). Hence, \(\phi_i(v)\neq\phi_i(w_i)\) for each \(i\in\{1,2\}\). Since \(\phi_1(v)\neq\phi_2(v)\) and there are only two colors, it follows that \(\phi(w_1)\neq\phi(w_2)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcase .: \(G_2[X_2]\) contains an induced \(C_4\). We first prove that \(X_1\) is a clique of \(G_1\). Suppose, for a contradiction, that \(X_1\) contains two vertices \(x\) and \(x'\) that are nonadjacent in \(G_1\). Let \(C\) be a subset of \(X_2\) that induces a \(C_4\) in \(G_2\). Since \(\alpha=\mathsf{p}\), every vertex of \(X_1\) is adjacent in \(G\) to every vertex of \(X_2\). Hence, \(C\cup\{x,x'\}\) induces \(\overline{3K_2}\) in \(G\), contradicting the balancedness of \(G\). Thus, \(X_1\) is a clique of \(G_1\). Hence, \(X_1\cup\{v\}\) and \(X_1\cup\{v'\}\) are maximal cliques of \(H_1^+\), because each of \(v\) and \(v'\) is adjacent exactly to \(X_1\) in \(H_1^+\) and \(v\) and \(v'\) are nonadjacent in \(H_1^+\).

Since \(X_1\) is nonempty, let \(x\) be a vertex of \(X_1\). Since \(\alpha=\mathsf{p}\), the graph \(H_2\) is isomorphic to \(G[V(G_2)\cup\{x\}]\). Thus, as \(G\) is balanced, \(H_2\) is balanced. Hence, Lemma 1 yields a proper \(2\)-coloring \(\phi_2\) of \(W_2\) with respect to \(H_2\). Since \(H_2\) is balanced, its clique hypergraph \(\mathcal{C}(H_2)\) is balanced. Theorem 3 yields a proper \(2\)-coloring \(\psi_2\) of the induced subhypergraph \(\mathcal{C}(H_2)_{W_2-\{v\}}\).

We prove three claims that will be used in the subcases below.

Claim : If \(Q\) is a maximal clique of \(H_2\) contained in \(V(G_2)\) and \(\vert Q\cap W\vert\geq 2\), then \(Q\cap W\) is not monochromatic under \(\psi_2\). Indeed, since \(W_2-\{v\}=W\cap V(G_2)\) and \(Q\subseteq V(G_2)\), we have \(Q\cap W=Q\cap(W_2-\{v\})\). Hence, \(\vert Q\cap(W_2-\{v\})\vert\geq 2\) and, by the choice of \(\psi_2\), \(Q\cap(W_2-\{v\})\) is not monochromatic under \(\psi_2\). Therefore, \(Q\cap W\) is not monochromatic under \(\psi_2\). This proves the claim.

Claim : If \(Q\) is a maximal clique of \(H^+\) and \(Q\subseteq V(G_2)\), then \(Q\) is a maximal clique of \(H_2\). Since \(G_2\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(G_2\). Thus, if \(Q\) were not maximal in \(H_2\), then \(v\) would be complete to \(Q\) in \(H_2\) and hence \(Q\subseteq X_2\). Since \(X_1\) is nonempty and complete to \(X_2\) in \(H^+\), any vertex of \(X_1\) would be complete to \(Q\) in \(H^+\), contradicting the maximality of \(Q\) in \(H^+\). Thus, \(Q\) is a maximal clique of \(H_2\). This proves the claim.

Claim : If \(Q\) is a maximal clique of \(H^+\) contained in neither \(V(H_1^+)\) nor \(V(G_2)\), then \(Q=X_1\cup R_2\), where \(R_2\) is a maximal clique of \(G_2[X_2]\) and \(R_2\cup\{v\}\) is a maximal clique of \(H_2\). Since \(V(H_1^+)\) and \(V(G_2)\) partition \(V(H^+)\), \(Q\) meets both \(V(H_1^+)\) and \(V(G_2)\). As neither \(v\) nor \(v'\) is adjacent in \(H^+\) to a vertex of \(G_2\), \(Q\) meets both \(V(G_1)\) and \(V(G_2)\) and is contained in \(V(G)\). Since \(G\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(G\). Since \(X_1\) is a clique of \(G_1\), Lemma 3 implies that \(Q=X_1\cup R_2\), where \(R_2\) is a maximal clique of \(G_2[X_2]\). Since \(N_{H_2}(v)=X_2\), the maximality of \(R_2\) in \(G_2[X_2]\) implies that \(R_2\cup\{v\}\) is a maximal clique of \(H_2\). This proves the claim.

We now consider three subcases according to the size of \(X_1\cap W\).

Subcase ..: \(\vert X_1\cap W\vert\geq 2\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\psi_2\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(H_1^+)\). Since \(H_1^+\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(H_1^+\). Since \(Q\cap W=Q\cap W_1\), the properness of \(\phi_1\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1\) and hence not monochromatic under \(\phi\). Suppose now that \(Q\subseteq V(G_2)\). By Claim [claim:pendant-H2], \(Q\) is a maximal clique of \(H_2\). By Claim [claim:psi2-G2], \(Q\cap W\) is not monochromatic under \(\psi_2\). Since \(Q\cap W\subseteq W_2-\{v\}\) and \(\phi\) agrees with \(\psi_2\) on \(W_2-\{v\}\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(H_1^+)\) nor \(V(G_2)\). Thus, Claim [claim:pendant-mixed] implies that \(X_1\subseteq Q\). Since \(X_1\cup\{v'\}\) is a maximal clique of \(H_1^+\) and \((X_1\cup\{v'\})\cap W_1=X_1\cap W\), the properness of \(\phi_1\) implies that \(X_1\cap W\) is not monochromatic under \(\phi_1\). Since \(X_1\cap W\subseteq Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcase ..: \(\vert X_1\cap W\vert=1\). Let \(w_1\) be the unique vertex of \(X_1\cap W\). Since \(X_1\cup\{v\}\) is a maximal clique of \(H_1^+\), the properness of \(\phi_1\) applied to \((X_1\cup\{v\})\cap W_1=\{w_1,v\}\) implies \(\phi_1(w_1)\neq\phi_1(v)\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_2(v)=\phi_1(w_1)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\phi_2\vert_{W_2-\{v\}}\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(H_1^+)\). Since \(H_1^+\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(H_1^+\). Since \(Q\cap W=Q\cap W_1\), the properness of \(\phi_1\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1\) and hence not monochromatic under \(\phi\). Suppose now that \(Q\subseteq V(G_2)\). By Claim [claim:pendant-H2], \(Q\) is a maximal clique of \(H_2\). Since \(Q\cap W=Q\cap W_2\), the properness of \(\phi_2\) implies that \(Q\cap W\) is not monochromatic under \(\phi_2\). Since \(Q\cap W\subseteq W_2-\{v\}\) and \(\phi\) agrees with \(\phi_2\) on \(W_2-\{v\}\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(H_1^+)\) nor \(V(G_2)\). Thus, by Claim [claim:pendant-mixed], \(Q=X_1\cup R_2\) for some \(R_2\subseteq X_2\) such that \(R_2\cup\{v\}\) is a maximal clique of \(H_2\). Since \(\vert Q\cap W\vert\geq 2\) and \(X_1\cap W=\{w_1\}\), \(R_2\cap W\) is nonempty. Since \(v\in W_2\), we have \(\vert (R_2\cup\{v\})\cap W_2\vert\geq 2\). The properness of \(\phi_2\) ensures the existence of \(w_2\in R_2\cap W\) such that \(\phi_2(w_2)\neq\phi_2(v)\). Hence, \(w_2\in Q\cap W\) and \(\phi(w_2)=\phi_2(w_2)\neq\phi_2(v)=\phi_1(w_1)=\phi(w_1)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcase ..: \(X_1\cap W=\emptyset\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_1}=\phi_1\) and \(\phi\vert_{W_2-\{v\}}=\psi_2\). Let \(Q\) be a maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(H_1^+)\). Since \(H_1^+\) is an induced subgraph of \(H^+\), \(Q\) is a maximal clique of \(H_1^+\). Since \(Q\cap W=Q\cap W_1\), the properness of \(\phi_1\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1\) and hence not monochromatic under \(\phi\). Suppose now that \(Q\subseteq V(G_2)\). By Claim [claim:pendant-H2], \(Q\) is a maximal clique of \(H_2\). By Claim [claim:psi2-G2], \(Q\cap W\) is not monochromatic under \(\psi_2\). Since \(Q\cap W\subseteq W_2-\{v\}\) and \(\phi\) agrees with \(\psi_2\) on \(W_2-\{v\}\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(H_1^+)\) nor \(V(G_2)\). Thus, by Claim [claim:pendant-mixed], \(Q=X_1\cup R_2\) for some \(R_2\subseteq X_2\) such that \(R_2\cup\{v\}\) is a maximal clique of \(H_2\). Since \(X_1\cap W=\emptyset\), we have \(Q\cap W=(R_2\cup\{v\})\cap W\cap V(G_2)\). Since \(\vert Q\cap W\vert\geq 2\) and \(R_2\cup\{v\}\) is a maximal clique of \(H_2\), the properness of \(\psi_2\) implies that \(Q\cap W\) is not monochromatic under \(\psi_2\) and hence not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H^+\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H^+\).

Subcases 3.1 and 3.2 cover all possibilities in the case \(\alpha=\mathsf{p}\) and, in each of them, \(W\) admits a proper \(2\)-coloring with respect to \(H^+\). We have reached the same conclusion in the cases where \(\alpha=\mathsf{f}\) or \(\alpha=\mathsf{t}\). Since \(W\) is an arbitrary subset of \(V(H^+)\) with \(v\in W\) and \(v'\notin W\), Lemma 2 implies that \(H^+\) is balanced. This proves assertion [item:2vertices].

Proof of assertion [item:1vertex]. Assume that no induced \(\overline{3K_2}\) of \(H\) contains \(v\). We will prove that \(H\) is balanced.

We again consider three cases according to the value of \(\alpha\).

Case : \(\alpha=\mathsf{f}\). Thus, \(H_i=H[V(G_i)\cup\{v\}]\) and no induced \(\overline{3K_2}\) of \(H_i\) contains \(v\), for each \(i\in\{1,2\}\). Since assertion [item:1vertex] holds for \(T_i\), \(H_i\) is balanced for each \(i\in\{1,2\}\).

Let \(W\) be an arbitrary subset of \(V(H)\). By Lemma 1, to prove that \(H\) is balanced, it suffices to give a proper \(2\)-coloring of \(W\) with respect to \(H\).

For each \(i\in\{1,2\}\), let \(W_i=W\cap V(H_i)\). Since both \(H_1\) and \(H_2\) are balanced, Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i\). If \(v\in W\), interchange the colors of \(\phi_2\) if necessary so that \(\phi_1(v)=\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_i}=\phi_i\) for each \(i\in\{1,2\}\). This is well defined because \(W_1\cup W_2=W\) and either \(W_1\cap W_2=\emptyset\) or \(W_1\cap W_2=\{v\}\) with the two colorings agreeing on \(v\).

Let \(Q\) be a maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\). In this case, there are no edges of \(H\) with one endpoint in \(V(G_1)\) and the other in \(V(G_2)\). Hence, \(Q\subseteq V(H_i)\) for some \(i\in\{1,2\}\). Thus, as \(H_i\) is an induced subgraph of \(H\), \(Q\) is a maximal clique of \(H_i\). Since \(Q\cap W=Q\cap W_i\) and \(\vert Q\cap W_i\vert\geq 2\), by the properness of \(\phi_i\), \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H\). Since \(W\) is an arbitrary subset of \(V(H)\), Lemma 1 implies that \(H\) is balanced in this case.

Case : \(\alpha=\mathsf{t}\). Thus, \(H_i=H[V(G_i)\cup\{v\}]\) and no induced \(\overline{3K_2}\) of \(H_i\) contains \(v\), for each \(i\in\{1,2\}\). Since assertion [item:1vertex] holds for \(T_i\), \(H_i\) is balanced for each \(i\in\{1,2\}\).

Let \(W\) be an arbitrary subset of \(V(H)\). By Lemma 1, to prove that \(H\) is balanced, it suffices to give a proper \(2\)-coloring of \(W\) with respect to \(H\).

We prove three claims about maximal cliques of \(H\) that will be used in the subcases below.

Claim : If \(Q\) is a maximal clique of \(H\) and \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\), then \(Q\) is a maximal clique of both \(H_i\) and \(H_i^+\). Thus, as \(H_i\) is an induced subgraph of \(H\), \(Q\) is a maximal clique of \(H_i\). Moreover, \(Q\) is not contained in \(X_i\), since otherwise \(Q\cup\{v\}\) would be a clique of \(H_i\), contradicting the maximality of \(Q\) in \(H_i\). As \(v'\) is adjacent exactly to \(X_i\) in \(H_i^+\), the vertex \(v'\) is not complete to \(Q\). Hence, \(Q\) is also a maximal clique of \(H_i^+\). This proves the claim.

Claim : If \(Q\) is a maximal clique of \(H\) contained in neither \(V(G_1)\) nor \(V(G_2)\), then \(Q=R_1\cup R_2\cup\{v\}\), where \(R_i\) is a maximal clique of \(G_i[X_i]\) for each \(i\in\{1,2\}\). Moreover, for each \(i\in\{1,2\}\), both \(R_i\cup\{v\}\) and \(R_i\cup\{v'\}\) are maximal cliques of \(H_i^+\). In particular, \(R_i\cup\{v\}\) is a maximal clique of \(H_i\) for each \(i\in\{1,2\}\). For each \(i\in\{1,2\}\), let \(R_i=Q\cap V(G_i)\). We first prove that \(R_i\neq\emptyset\) for each \(i\in\{1,2\}\). By symmetry, suppose, for a contradiction, that \(R_2=\emptyset\). Since \(Q\) is not contained in \(V(G_1)\), we have \(v\in Q\). As \(Q\) is a clique and \(N_H(v)\cap V(G_1)=X_1\), it follows that \(Q\subseteq X_1\cup\{v\}\). Since \(X_2\) is nonempty and complete to \(X_1\cup\{v\}\) in \(H\), a vertex of \(X_2\) is complete to \(Q\) in \(H\), contradicting the maximality of \(Q\) in \(H\). This contradiction proves that indeed \(R_1\) and \(R_2\) are nonempty.

For each \(i\in\{1,2\}\), every vertex of \(R_i\) has a neighbor outside \(V(G_i)\) in \(H\), because \(R_{3-i}\) is nonempty and \(Q\) is a clique. Hence, \(R_i\subseteq X_i\) for each \(i\in\{1,2\}\). If \(v\notin Q\), then \(Q=R_1\cup R_2\) and \(Q\cup\{v\}\) is a clique of \(H\), contradicting the maximality of \(Q\) in \(H\). Thus, \(v\in Q\) and so \(Q=R_1\cup R_2\cup\{v\}\). As \(G\) is an induced subgraph of \(H\), the set \(Q-\{v\}\) is a clique of \(G\). Moreover, \(Q-\{v\}\) is maximal in \(G\), since any vertex of \(G\) complete to \(Q-\{v\}\) in \(G\) would belong to \(X_1\cup X_2\) (because \(Q-\{v\}\) meets both \(V(G_1)\) and \(V(G_2)\)) and thus would be adjacent to \(v\) in \(H\), contradicting the maximality of \(Q\) in \(H\). Hence, by Lemma 3, \(R_i\) is a maximal clique of \(G_i[X_i]\) for each \(i\in\{1,2\}\). This proves the first assertion of the claim.

Let \(i\in\{1,2\}\). Since \(R_i\subseteq X_i\), both \(R_i\cup\{v\}\) and \(R_i\cup\{v'\}\) are cliques of \(H_i^+\). They are maximal because \(v\) and \(v'\) are nonadjacent in \(H_i^+\) and any vertex of \(G_i\) complete to one of them would belong to \(X_i-R_i\) and would be complete to \(R_i\) in \(G_i[X_i]\), contradicting the maximality of \(R_i\) in \(G_i[X_i]\). Since \(H_i\) is an induced subgraph of \(H_i^+\), it follows that \(R_i\cup\{v\}\) is a maximal clique of \(H_i\). Since \(i\in\{1,2\}\) was arbitrary, this completes the proof of the claim.

We consider three subcases.

Subcase .: \(v\in W\). For each \(i\in\{1,2\}\), let \(W_i=W\cap V(H_i)\). Since \(H_i\) is balanced for each \(i\in\{1,2\}\), Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_1(v)=\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W_i}=\phi_i\) for each \(i\in\{1,2\}\). This is well defined because \(W_1\cup W_2=W\), \(W_1\cap W_2=\{v\}\), and the two colorings agree on \(v\).

Let \(Q\) be a maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). By Claim [claim:contained-cliques], \(Q\) is a maximal clique of \(H_i\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W\) is not monochromatic under \(\phi_i\). As \(\phi\) agrees with \(\phi_i\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). By Claim [claim:mixed-core], \(Q=R_1\cup R_2\cup\{v\}\), where \(R_i\subseteq X_i\) and \(R_i\cup\{v\}\) is a maximal clique of \(H_i\) for each \(i\in\{1,2\}\). Since \(v\in W\) and \(\vert Q\cap W\vert\geq 2\), there is some \(i\in\{1,2\}\) such that \((R_i\cup\{v\})\cap W_i\) has at least two vertices. By the properness of \(\phi_i\), \((R_i\cup\{v\})\cap W_i\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(W_i\) and \((R_i\cup\{v\})\cap W_i\subseteq Q\cap W\), it follows that \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H\) in this subcase.

Subcase .: \(v\notin W\) and neither \(G_1[X_1]\) nor \(G_2[X_2]\) contains an induced \(C_4\). For each \(i\in\{1,2\}\), no induced \(\overline{3K_2}\) of \(H_i^+\) contains both \(v\) and \(v'\), since otherwise the four remaining vertices would lie in \(X_i\) and induce a \(C_4\) in \(G_i[X_i]\). Thus, by assertion [item:2vertices] for \(T_i\), \(H_i^+\) is balanced for each \(i\in\{1,2\}\).

For each \(i\in\{1,2\}\), let \(W_i=(W\cap V(G_i))\cup\{v\}\). Since \(H_i^+\) is balanced for each \(i\in\{1,2\}\), Lemma 1 yields, for each \(i\in\{1,2\}\), a proper \(2\)-coloring \(\phi_i\) of \(W_i\) with respect to \(H_i^+\). Interchanging the colors of \(\phi_2\) if necessary, we assume that \(\phi_1(v)\neq\phi_2(v)\). Let \(\phi\) be the \(2\)-coloring of \(W\) such that \(\phi\vert_{W\cap V(G_i)}=\phi_i\vert_{W\cap V(G_i)}\) for each \(i\in\{1,2\}\). This is well defined because \(W\subseteq V(G)\) and \(V(G_1)\) and \(V(G_2)\) partition \(V(G)\).

Let \(Q\) be a maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_i)\) for some \(i\in\{1,2\}\). By Claim [claim:contained-cliques], \(Q\) is a maximal clique of \(H_i^+\). Since \(Q\cap W=Q\cap W_i\), the properness of \(\phi_i\) implies that \(Q\cap W\) is not monochromatic under \(\phi_i\). As \(\phi\) agrees with \(\phi_i\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). By Claim [claim:mixed-core], \(Q=R_1\cup R_2\cup\{v\}\), where, for each \(i\in\{1,2\}\), \(R_i\) is a maximal clique of \(G_i[X_i]\) and both \(R_i\cup\{v\}\) and \(R_i\cup\{v'\}\) are maximal cliques of \(H_i^+\). Since \(v\notin W\), it follows that \(Q\cap W=(R_1\cap W)\cup(R_2\cap W)\). Suppose first that \(\vert R_i\cap W\vert\geq 2\) for some \(i\in\{1,2\}\). Since \((R_i\cup\{v'\})\cap W_i=R_i\cap W\), the properness of \(\phi_i\) implies that \(R_i\cap W\) is not monochromatic under \(\phi_i\). Since \(\phi\) agrees with \(\phi_i\) on \(R_i\cap W\) and \(R_i\cap W\subseteq Q\cap W\), it follows that \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(\vert R_i\cap W\vert\leq 1\) for each \(i\in\{1,2\}\). Since \(\vert Q\cap W\vert\geq 2\), we have \(\vert R_i\cap W\vert=1\) for each \(i\in\{1,2\}\). Let \(w_i\) be the unique vertex of \(R_i\cap W\). Since \((R_i\cup\{v\})\cap W_i=\{w_i,v\}\), the properness of \(\phi_i\) implies that \(\phi_i(w_i)\neq\phi_i(v)\) for each \(i\in\{1,2\}\). As there are only two colors and \(\phi_1(v)\neq\phi_2(v)\), it follows that \(\phi(w_1)\neq\phi(w_2)\). Thus, \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H\) in this subcase.

Subcase .: \(v\notin W\) and \(G_i[X_i]\) contains an induced \(C_4\) for some \(i\in\{1,2\}\). By symmetry, suppose that \(G_1[X_1]\) contains an induced \(C_4\). We first show that \(X_2\) is a clique of \(G_2\). Suppose, for a contradiction, that \(X_2\) contains two vertices \(x_2\) and \(y_2\) that are nonadjacent in \(G_2\). Let \(C\) be a subset of \(X_1\) inducing a \(C_4\) in \(G_1\). Since \(X_1\) is complete to \(X_2\) in \(G\), \(C\cup\{x_2,y_2\}\) induces \(\overline{3K_2}\) in \(G\), contradicting the balancedness of \(G\). Hence, \(X_2\) is a clique of \(G_2\). In particular, \(G_2[X_2]\) contains no induced \(C_4\). Therefore, by assertion [item:2vertices] for \(T_2\), \(H_2^+\) is balanced.

Let \(W_1=W\cap V(G_1)\), let \(W_1^v=(W\cap V(G_1))\cup\{v\}\), and let \(W_2=(W\cap V(G_2))\cup\{v\}\). Since \(H_1\) and \(H_2^+\) are balanced, Lemma 1 yields a proper \(2\)-coloring \(\phi_1\) of \(W_1\) with respect to \(H_1\), a proper \(2\)-coloring \(\phi_1^v\) of \(W_1^v\) with respect to \(H_1\), and a proper \(2\)-coloring \(\phi_2\) of \(W_2\) with respect to \(H_2^+\). If \(\vert X_2\cap W\vert=1\), let \(w_2\) be the unique vertex of \(X_2\cap W\) and interchange the colors of \(\phi_1^v\) if necessary so that \(\phi_1^v(v)=\phi_2(w_2)\). Let \(\phi\) be the \(2\)-coloring of \(W\) defined as follows. If \(\vert X_2\cap W\vert=1\), set \(\phi\vert_{W\cap V(G_1)}=\phi_1^v\vert_{W\cap V(G_1)}\) and \(\phi\vert_{W\cap V(G_2)}=\phi_2\vert_{W\cap V(G_2)}\). Otherwise, set \(\phi\vert_{W\cap V(G_1)}=\phi_1\) and \(\phi\vert_{W\cap V(G_2)}=\phi_2\vert_{W\cap V(G_2)}\).

Let \(Q\) be a maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\). Suppose first that \(Q\subseteq V(G_1)\). By Claim [claim:contained-cliques], \(Q\) is a maximal clique of \(H_1\). Since \(Q\subseteq V(G_1)\), we have \(Q\cap W=Q\cap W_1=Q\cap W_1^v\). If \(\vert X_2\cap W\vert=1\), then the properness of \(\phi_1^v\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1^v\) and, since \(\phi\) agrees with \(\phi_1^v\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). If \(\vert X_2\cap W\vert\neq 1\), then the properness of \(\phi_1\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1\) and, since \(\phi\) agrees with \(\phi_1\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Suppose now that \(Q\subseteq V(G_2)\). By Claim [claim:contained-cliques], \(Q\) is a maximal clique of \(H_2^+\). Since \(Q\cap W=Q\cap W_2\), the properness of \(\phi_2\) implies that \(Q\cap W\) is not monochromatic under \(\phi_2\). As \(\phi\) agrees with \(\phi_2\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). It only remains to consider the case where \(Q\) is contained in neither \(V(G_1)\) nor \(V(G_2)\). Since \(X_2\) is a clique of \(G_2\), Claim [claim:mixed-core] implies that \(Q=R_1\cup X_2\cup\{v\}\), where \(R_1\) is a maximal clique of \(G_1[X_1]\), \(X_2\cup\{v'\}\) is a maximal clique of \(H_2^+\), and \(R_1\cup\{v\}\) is a maximal clique of \(H_1\). Suppose first that \(\vert X_2\cap W\vert\geq 2\). Since \((X_2\cup\{v'\})\cap W_2=X_2\cap W\), the properness of \(\phi_2\) implies that \(X_2\cap W\) is not monochromatic under \(\phi_2\). Since \(\phi\) agrees with \(\phi_2\) on \(X_2\cap W\) and \(X_2\cap W\subseteq Q\cap W\), it follows that \(Q\cap W\) is not monochromatic under \(\phi\). Suppose next that \(X_2\cap W=\emptyset\). In this case, \(Q\cap W=R_1\cap W\). Since \((R_1\cup\{v\})\cap W_1=R_1\cap W=Q\cap W\), the properness of \(\phi_1\) implies that \(Q\cap W\) is not monochromatic under \(\phi_1\). As \(\phi\) agrees with \(\phi_1\) on \(Q\cap W\), \(Q\cap W\) is not monochromatic under \(\phi\). Finally, suppose that \(\vert X_2\cap W\vert=1\) and let \(w_2\) be the unique vertex of \(X_2\cap W\). Since \(\vert Q\cap W\vert\geq 2\) and \(X_2\cap W=\{w_2\}\), \(R_1\cap W\) is nonempty. Since \((R_1\cup\{v\})\cap W_1^v\) contains \(v\) and at least one vertex of \(R_1\cap W\), by the properness of \(\phi_1^v\), there exists a vertex \(w_1\in R_1\cap W\) such that \(\phi_1^v(w_1)\neq\phi_1^v(v)=\phi_2(w_2)\). Hence, \(Q\cap W\) is not monochromatic under \(\phi\). Since \(Q\) is an arbitrary maximal clique of \(H\) such that \(\vert Q\cap W\vert\geq 2\), \(\phi\) is a proper \(2\)-coloring of \(W\) with respect to \(H\) in this subcase.

The three subcases above cover all possibilities and, in each of them, \(W\) admits a proper \(2\)-coloring with respect to \(H\). Since \(W\) is an arbitrary subset of \(V(H)\), Lemma 1 implies that \(H\) is balanced in this case.

Case : \(\alpha=\mathsf{p}\). We first prove that no induced \(\overline{3K_2}\) of \(H^+\) contains both \(v\) and \(v'\). Suppose, for a contradiction, that such an induced subgraph exists. Since \(v\) and \(v'\) are false twins with common neighborhood \(\mathop{\mathrm{TS}}(T)=X_1\), the other four vertices lie in \(X_1\) and induce a \(C_4\) in \(G_1[X_1]\). By Remark 5, \(X_2\) is nonempty. Let \(x_2\) be a vertex of \(X_2\). Since \(\alpha=\mathsf{p}\), \(x_2\) is adjacent in \(H\) to every vertex of \(X_1\) and is nonadjacent to \(v\) in \(H\). Thus, replacing \(v'\) by \(x_2\) produces an induced \(\overline{3K_2}\) of \(H\) containing \(v\), contradicting the assumption that no induced \(\overline{3K_2}\) of \(H\) contains \(v\). Hence, no induced \(\overline{3K_2}\) of \(H^+\) contains both \(v\) and \(v'\). By assertion [item:2vertices], already proved for \(T\), \(H^+\) is balanced. Since \(H=H^+-v'\) and the class of balanced graphs is hereditary, \(H\) is balanced in this case.

The three cases above prove assertion [item:1vertex]. Together with the proof of assertion [item:2vertices], this shows that, assuming \(G\) is balanced and that both assertions hold for \(T_1\) and \(T_2\), both assertions hold for \(T\). Since the base case was proved at the beginning, this completes the induction and the proof of the proposition. ◻

Proof. The implication \({\eqref{item:DH-balanced}}\Rightarrow{\eqref{item:DH-HCH}}\) follows from Theorem 2. The implication \({\eqref{item:DH-HCH}}\Rightarrow{\eqref{item:DH-no-co3K2}}\) follows because \(\overline{3K_2}\) is not clique-Helly. Indeed, if \(aa'\), \(bb'\), and \(cc'\) are its nonedges, then the maximal cliques \(\{a,b,c'\}\), \(\{a,b',c\}\), and \(\{a',b,c\}\) are pairwise intersecting and have empty total intersection.

It only remains to prove \({\eqref{item:DH-no-co3K2}}\Rightarrow{\eqref{item:DH-balanced}}\). By Theorem 6, it suffices to prove that, for each \(\mathop{\mathrm{OVE}}\)-tree \(T\), if \(G=\mathop{\mathrm{DH}}(T)\) and \(G\) contains no induced \(\overline{3K_2}\), then \(G\) is balanced. We proceed by induction on the definition of \(\mathop{\mathrm{OVE}}\)-trees.

If \(T\) has exactly one vertex and \(G=\mathop{\mathrm{DH}}(T)\), then \(G\) has one vertex and is balanced.

We now consider the case where \(T=T_1\oplus_\alpha T_2\) for some \(\alpha\in\{\mathsf{f},\mathsf{t},\mathsf{p}\}\). Let \(G=\mathop{\mathrm{DH}}(T)\) and suppose that \(G\) contains no induced \(\overline{3K_2}\). Let \(G_i=\mathop{\mathrm{DH}}(T_i)\) and \(X_i=\mathop{\mathrm{TS}}(T_i)\) for each \(i\in\{1,2\}\). By Remark 5, \(G_i\) is an induced subgraph of \(G\) for each \(i\in\{1,2\}\). In particular, neither \(G_1\) nor \(G_2\) contains an induced \(\overline{3K_2}\). Hence, by the induction hypothesis applied to \(T_i\), \(G_i\) is balanced for each \(i\in\{1,2\}\).

If \(\alpha=\mathsf{f}\), then \(G=G_1\cup G_2\). Since \(G_1\) and \(G_2\) are balanced and the maximal cliques of \(G\) are precisely the maximal cliques of \(G_1\) and \(G_2\), \(G\) is balanced. Thus, in the remainder of the proof, we only consider the case where \(\alpha\in\{\mathsf{t},\mathsf{p}\}\). Let \(v\) be a vertex not in \(V(G)\). For each \(i\in\{1,2\}\), let \(H_i\) be the graph that arises from \(G_i\) by adding \(v\) such that \(N_{H_i}(v)=X_i\). Thus, \(V(H_1)\cap V(H_2)=\{v\}\) and, by Definition 2, \(G=H_1\ast H_2\).

Claim : \(H_i\) is balanced for each \(i\in\{1,2\}\). Let \(i\in\{1,2\}\). By Remark 5, \(X_{3-i}\) is nonempty. Let \(x\) be a vertex of \(X_{3-i}\). If \(H_i\) contained an induced \(\overline{3K_2}\) containing \(v\), then replacing \(v\) by \(x\) would produce an induced \(\overline{3K_2}\) in \(G\), because \(x\) has in \(G\) the same neighbors in \(V(G_i)\) as \(v\) has in \(H_i\). This contradicts the assumption that \(G\) contains no induced \(\overline{3K_2}\). Hence, \(H_i\) contains no induced \(\overline{3K_2}\) containing \(v\). Since \(G_i\) is balanced, Proposition 10[item:1vertex] applied to \(T_i\) implies that \(H_i\) is balanced. This proves the claim.

For each \(i\in\{1,2\}\), let \(H_i^+\) be the graph that arises from \(H_i\) by adding a false twin \(v'\) of \(v\).

Claim : For each \(i\in\{1,2\}\), if \(X_{3-i}\) is not a clique of \(G_{3-i}\), then \(H_i^+\) is balanced. Let \(i\in\{1,2\}\) and suppose that \(X_{3-i}\) is not a clique of \(G_{3-i}\). Let \(x\) and \(x'\) be two vertices of \(X_{3-i}\) that are nonadjacent in \(G_{3-i}\). If \(H_i^+\) contained an induced \(\overline{3K_2}\) containing \(v\) and \(v'\), then replacing \(v\) and \(v'\) by \(x\) and \(x'\), respectively, would produce an induced \(\overline{3K_2}\) in \(G\). This replacement is valid because \(x\) and \(x'\) are nonadjacent in \(G\) and have in \(G\) the same neighbors in \(V(G_i)\) as \(v\) and \(v'\) have in \(H_i^+\). This contradicts the assumption that \(G\) contains no induced \(\overline{3K_2}\). Hence, no induced \(\overline{3K_2}\) of \(H_i^+\) contains both \(v\) and \(v'\). By Proposition 10[item:2vertices] applied to \(T_i\), \(H_i^+\) is balanced. This proves the claim.

We now apply Proposition 8 according to the three possible clique alternatives for \(X_1\) in \(G_1\) and \(X_2\) in \(G_2\).

Case : \(X_1\) and \(X_2\) are both cliques of \(G_1\) and \(G_2\), respectively. In this case, since \(H_1\) and \(H_2\) are balanced by Claim [claim:main-Hi-balanced], Proposition 8[item:TSareCliques] implies that \(G\) is balanced.

Case : For some \(i\in\{1,2\}\), \(X_i\) is a clique of \(G_i\) and \(X_{3-i}\) is not a clique of \(G_{3-i}\). For this index \(i\), Claim [claim:main-Hi43-balanced] implies that \(H_i^+\) is balanced. Moreover, \(H_{3-i}\) is balanced by Claim [claim:main-Hi-balanced]. Hence, Proposition 8[item:TS1isClique] applied to \(H_i\) and \(H_{3-i}\) in place of \(H_1\) and \(H_2\) implies that \(H_i\ast H_{3-i}\) is balanced. Since \(H_i\ast H_{3-i}=G\), \(G\) is balanced.

Case : Neither \(X_1\) is a clique of \(G_1\) nor \(X_2\) is a clique of \(G_2\). In this case, Claim [claim:main-Hi43-balanced] applied with \(i=1\) and \(i=2\) implies that \(H_1^+\) and \(H_2^+\) are balanced, respectively. Hence, by Proposition 8[item:TSareNotCliques], \(G\) is balanced.

Together with the case \(\alpha=\mathsf{f}\) considered above, the three cases above complete the inductive step. Since the base case was proved above, this completes the induction and the proof of the theorem. ◻

Proof. We first prove that \(\mathop{\mathrm{cert}}(T)\) is a certificate tuple for \(T\). Let \(T\) be an \(\mathop{\mathrm{OVE}}\)-tree. We proceed by induction on the definition of \(\mathop{\mathrm{OVE}}\)-trees. Let \(G=\mathop{\mathrm{DH}}(T)\) and \(X=\mathop{\mathrm{TS}}(T)\).

If \(T\) has exactly one vertex, then \(G\) has one vertex. Hence, the algorithm returns \((\mathop{\mathrm{\emptyset}},\mathop{\mathrm{\emptyset}},\mathop{\mathrm{\emptyset}},\mathop{\mathrm{\emptyset}})\), which is a certificate tuple for \(T\).

Suppose now that \(T=T_1\oplus_\alpha T_2\) for some \(\alpha\in\{\mathsf{f},\mathsf{t},\mathsf{p}\}\). Let \(G_i=\mathop{\mathrm{DH}}(T_i)\) and \(X_i=\mathop{\mathrm{TS}}(T_i)\) for each \(i\in\{1,2\}\). By the induction hypothesis, the recursive calls in lines [line:rec1] and [line:rec2] of Algorithm 4 return certificate tuples \(\mathop{\mathrm{cert}}(T_1)\) and \(\mathop{\mathrm{cert}}(T_2)\), respectively. We will prove that the output \(\mathop{\mathrm{cert}}(T)\) of Algorithm 4 is a certificate tuple for \(T\).

Claim : Suppose that \(\alpha\in\{\mathsf{t},\mathsf{p}\}\). If \(S\) is the vertex set of an induced \(\overline{3K_2}\) in \(G\) and \(S\) is contained in neither \(V(G_1)\) nor \(V(G_2)\), then, for some \(i\in\{1,2\}\), either \(S=C\cup N\), where \(C\) is the vertex set of an induced \(C_4\) in \(G_i[X_i]\) and \(N\) is a pair of nonadjacent vertices of \(G_{3-i}[X_{3-i}]\), or \(S=Y\cup\{x\}\), where \(Y\) induces in \(G_i\) a \(W_4\) in which the vertices of the \(4\)-cycle lie in \(X_i\), the universal vertex lies in \(V(G_i)-X_i\), and \(x\in X_{3-i}\). Let \(S_i=S\cap V(G_i)\) for each \(i\in\{1,2\}\). Suppose first that \(\vert S_1\vert\geq 2\) and \(\vert S_2\vert\geq 2\). Thus, for each \(i\in\{1,2\}\), each vertex of \(S_i\) has at least one neighbor in \(S_{3-i}\) and, necessarily, \(S_i\subseteq X_i\). Hence, \(S_1\) is complete to \(S_2\) in \(G\). Consequently, for some \(i\in\{1,2\}\), \(S_i\) induces a \(C_4\) in \(G_i[X_i]\) and \(S_{3-i}\) is a pair of nonadjacent vertices of \(G_{3-i}[X_{3-i}]\). Taking \(C=S_i\) and \(N=S_{3-i}\), the first alternative holds. By symmetry, it only remains to consider the case where \(\vert S_2\vert=1\). Let \(x\) be the unique vertex of \(S_2\). Since \(x\) has exactly one nonneighbor in \(S_1\) and is adjacent to the other four vertices of \(S_1\), \(x\) belongs to \(X_2\), its nonneighbor in \(S_1\) lies in \(V(G_1)-X_1\), and its four neighbors in \(S_1\) lie in \(X_1\). These four vertices induce a \(C_4\), and the remaining vertex of \(S_1\) is adjacent to all of them. Thus, taking \(Y=S_1\), the second alternative holds.

We consider three cases according to the value of \(\alpha\).

Case : \(\alpha=\mathsf{f}\). Since \(v_i\) is the root of \(T_i\) for each \(i\in\{1,2\}\), Remark 5 implies that \(v_i\in X_i\) for each \(i\in\{1,2\}\). Moreover, since \(G\) is the disjoint union of \(G_1\) and \(G_2\) and \(X=X_1\cup X_2\), \(v_1\) and \(v_2\) are nonadjacent vertices in \(G[X]\) and every induced \(C_4\) in \(G[X]\), every induced \(W_4\) of the type described in [it:certW], and every induced \(\overline{3K_2}\) in \(G\) is contained in either \(G_1\) or \(G_2\). Hence, the assignments in lines [line:f1]–[line:f4] make assertions [it:certN]–[it:certS] in the definition of a certificate tuple for \(T\) hold.

Case : \(\alpha=\mathsf{t}\). Since every nonedge of \(G[X]\) is contained in \(G_1[X_1]\) or in \(G_2[X_2]\), line [line:t1] makes [it:certN] hold. Also, any vertex set inducing a \(C_4\) in \(G[X]\) is either contained in \(X_1\), contained in \(X_2\), or is the union of a pair of nonadjacent vertices of \(G_1[X_1]\) and a pair of nonadjacent vertices of \(G_2[X_2]\). Hence, lines [line:t2]–[line:t5] make [it:certC] in the definition of a certificate tuple for \(T\) hold. We now prove that line [line:t6] makes [it:certW] in the definition of a certificate tuple for \(T\) hold. Suppose first that \(W^{(i)}\neq\mathop{\mathrm{\emptyset}}\) for some \(i\in\{1,2\}\). By the induction hypothesis, \(W^{(i)}\) is the vertex set of an induced \(W_4\) in \(G_i\) in which the vertices of the \(4\)-cycle lie in \(X_i\) and the universal vertex lies in \(V(G_i)-X_i\). Since \(G_i\) is an induced subgraph of \(G\), \(X_i\subseteq X\), and \(V(G_i)-X_i\subseteq V(G)-X\), if we let \(W=W^{(i)}\), then \(W\) satisfies [it:certW] in the definition of a certificate tuple for \(T\). Conversely, let \(W\neq\mathop{\mathrm{\emptyset}}\) be as in [it:certW] in the definition of a certificate tuple for \(T\). If the vertices of the \(4\)-cycle in \(G[W]\) were not contained in \(X_i\) for some \(i\in\{1,2\}\), then, since \(X_1\) is complete to \(X_2\), two of them would lie in \(X_1\) and the other two in \(X_2\). But the universal vertex of \(G[W]\) lies in \(V(G)-X\) and has neighbors in at most one of \(X_1\) and \(X_2\), a contradiction. Thus, the vertices of the \(4\)-cycle in \(G[W]\) are contained in \(X_i\) for some \(i\in\{1,2\}\), and thus the universal vertex of \(G[W]\) must lie in \(V(G_i)-X_i\). Consequently, \(W^{(i)}\neq\mathop{\mathrm{\emptyset}}\). Hence, such a vertex set \(W\) exists if and only if \(W^{(1)}\neq\mathop{\mathrm{\emptyset}}\) or \(W^{(2)}\neq\mathop{\mathrm{\emptyset}}\), and line [line:t6] makes [it:certW] in the definition of a certificate tuple for \(T\) hold. Finally, Claim [claim:cert-cross-obst] shows that lines [line:s1]–[line:s7] make [it:certS] in the definition of a certificate tuple for \(T\) hold.

Case : \(\alpha=\mathsf{p}\). Since \(X=X_1\), a nonedge of \(G[X]\) is exactly a nonedge of \(G_1[X_1]\), and an induced \(C_4\) in \(G[X]\) is exactly an induced \(C_4\) in \(G_1[X_1]\). Hence, the assignments in lines [line:p1] and [line:p2] make [it:certN] and [it:certC] in the definition of a certificate tuple for \(T\) hold. We now prove that line [line:p3] makes [it:certW] in the definition of a certificate tuple for \(T\) hold. Since \(X=X_1\), the vertices of the \(4\)-cycle of any induced \(W_4\) of the type described in [it:certW] in the definition of a certificate tuple for \(T\) lie in \(X_1\) and therefore induce a \(C_4\) in \(G_1[X_1]\). Hence, by the induction hypothesis, \(C^{(1)}\neq\mathop{\mathrm{\emptyset}}\). Conversely, if \(C^{(1)}\neq\mathop{\mathrm{\emptyset}}\), then \(C^{(1)}\) is the vertex set of an induced \(C_4\) in \(G_1[X_1]\). Since \(X_1\) is complete to \(X_2\) in \(G\) and \(v_2\in V(G)-X\), the set \(C^{(1)}\cup\{v_2\}\) induces the required \(W_4\) in \(G\). Hence, line [line:p3] makes [it:certW] in the definition of a certificate tuple for \(T\) hold. Finally, Claim [claim:cert-cross-obst] shows that lines [line:s1]–[line:s7] make [it:certS] in the definition of a certificate tuple for \(T\) hold.

It only remains to prove the linear-time bound. Each tree considered by the recursion is represented by its root and by the first child of the root that belongs to that tree, if any. Line [line:base] takes constant time. In addition, line [line:split] can be performed in constant time because \(v_1\) is the root of \(T\), \(v_2\) is the first child of \(v_1\) in \(T\), \(\alpha\) is the label of the edge \(v_1v_2\), the tree \(T_2\) is determined by the root \(v_2\) and by the first child of \(v_2\), if any, while \(T_1\) is determined by the root \(v_1\) and by the next sibling of \(v_2\) among the children of \(v_1\), if any. Moreover, lines [line:f1]–[line:return] can be performed in constant time because all involved vertex sets have size at most six. By the induction hypothesis, the recursive calls in lines [line:rec1] and [line:rec2] take linear time in \(T_1\) and \(T_2\), respectively. Thus, the total time is linear in \(T\). This completes the proof of the lemma. ◻

Proof. Let \(G\) be a distance-hereditary graph and consider the algorithm described above. By Theorem 7, an \(\mathop{\mathrm{OVE}}\)-tree \(T\) of \(G\) can be built in linear time. By Lemma 4, \(\mathop{\mathrm{cert}}(T)\) can also be computed in linear time and its last component \(S\) satisfies [it:certS]. Since \(G\) is distance-hereditary, Theorem 11 implies that \(G\) is balanced if and only if \(S=\mathop{\mathrm{\emptyset}}\). Hence, the whole algorithm is correct and can be completed in linear time. ◻