# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results
(From right to left:) Assume \(\mathcal{D}\) is strongly connected. Then by Lemma 6 we know that \(\mathcal{SM}\) and \(\mathcal{WM}\) are equivalent. From this and from the assumption that \(\mathcal{SM}\geq\mathcal{MM}\geq\mathcal{WM}\) it follows that \(\mathcal{SM}\) and \(\mathcal{MM}\) and \(\mathcal{WM}\) are equivalent. Since \(\mathcal{D}\) is strongly connected by Theorem 2 we know that \(\mathcal{WM}\) is a black and white SAT problem. We know that \(\mathcal{MM}\) and \(\mathcal{WM}\) are equivalent; hence, \(\mathcal{MM}\) is a black and white SAT problem. The following theorem shows that the Balatonboglar model of a communication graph is a transition between the strong and the weak model. Actually, Balatonboglar is a small city in Hungary next to lake Balaton. We spent quite a lot of time next to the lake thinking about a model which is 3-SAT and black and white if the directed graph is strongly connected. As the next theorem shows, we were successful. As a sign of appreciation for that great time, we gave the name Balatonboglar to that model. **Theorem 4**. : _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{BM}\) be a Balatonboglar model of \(\mathcal{D}\). Then \(\mathcal{BM}\) is a black and white 3-SAT problem if and only if \(\mathcal{D}\) is strongly connected._  
Proof. : Assume \(\mathcal{D}\) is a communication graph. Assume \(\mathcal{BM}\) is a Balatonboglar model of \(\mathcal{D}\). We show \(\mathcal{BM}\) is a black and white 3-SAT problem if and only if \(\mathcal{D}\) is strongly connected. Due to the construction of \(\mathcal{BM}\), it is a 3-SAT problem for any communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Let \(\mathcal{SM}\) be the strong model of \(\mathcal{D}\). Now we show that \(\mathcal{BM}\) is a black and white 3-SAT problem if and only if \(\mathcal{D}\) is strongly connected. From the transitions theorem (Theorem 3), we know that to show this, it is enough to show that \(\mathcal{SM}\geq\mathcal{BM}\geq\mathcal{WM}\). (I) As a first step, we show that \(\mathcal{SM}\geq\mathcal{BM}\). To show this it is enough to show that \(\mathcal{SM}\) subsumes all clauses from \(\mathcal{BM}\). Let \(C\) be an arbitrary but fixed element of \(\mathcal{BM}\). This means that \(C\) is either an element of \(NodeRep2\), or \(NodeRep3\), or \(TagForward\). If \(C\) is an element of \(NodeRep2\), then \(C\) is also element of \(\mathcal{SM}\), so this case is trivial. If \(C\) is an element of \(NodeRep3\), then, without loss of generality, we may assume that \(C=\{-a,b,c\}\), where \(a\) is a vertex in \(\mathcal{D}\) and \(b\in OutE(a)\) and \(c\in OutE(a)\) and \(b\
eq c\). From the construction of \(NodeRep3\) we know that in \(\mathcal{D}\) there are the following edges: \((a,b)\), \((a,c)\). Since \(\mathcal{SM}\) is generated from the same graph, by its definition we know that \(\mathcal{SM}\) contains the clauses \(\{-a,b\}\), \(\{\
eg a,c\}\) and both of them subsume \(C\). If \(C\) is an element of \(TagForward\), then, without loss of generality, we may assume that \(C=\{-d,\
eg e,f\}\), where \(d\) is a vertex in \(\mathcal{D}\), and \(e\in OutE(d)\) and \(f\in OutE(e)\). From the construction of \(TagForward\) we know that in \(\mathcal{D}\) there are the following edges: \((d,e)\), \((e,f)\). Since \(\mathcal{SM}\) is generated from the same graph, by its definition we know that \(\mathcal{SM}\) contains the clause \(\{-e,f\}\) which subsumes \(C\). (II) As a second step, we show \(\mathcal{BM}\geq\mathcal{WM}\). To show this it is enough to show that \(\mathcal{BM}\) subsumes all clauses from \(\mathcal{WM}\). Let \(C\) be an arbitrary but fixed element of \(\mathcal{WM}\). This means that \(C\) is an element of either \(NodeRep\) or \(Cycles\). If \(C\) is an element of \(NodeRep\), then, without loss of generality, we may assume that \(C=\{\
eg a,b_{1},b_{2},\ldots,b_{k}\}\), where \(k>0\). From the construction of \(NodeRep\) we know that in \(\mathcal{D}\) there are the following edges: \((a,b_{1}),(a,b_{2}),\ldots,(a,b_{k})\).