# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results  
This section is the main contribution of this work. We prove that the new models, the weak one and the Balatonboglar one, have the same property as the strong one; i.e., the model of a communication graph is a black and white SAT problem iff the graph is strongly connected. To be able to prove this, we need some auxiliary lemmas. The first one states that the weak model has at least two solutions, the white one and the black one. Lemma 1: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Then \(\mathcal{WM}\) has at least two solutions, namely, the white assignment (WW) and the black assignment (BB)._  
Proof: Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Since there is a positive and also a negative literal in each clause of \(\mathcal{WM}\), the white assignment (\(WW\)) and also the black assignment (\(BB\)) are solutions for \(\mathcal{WM}\). The second lemma states that if the weak model has only two solutions, then each cycle in the communication graph has at least one exit point, except the cycle which contains all vertices of the graph. Lemma 2: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Assume that \(\mathcal{WM}\) has only two solutions. Then for each cycle \(C\in Cycles\) we have that \(ExitPonts(C)\) is not empty or \(C\) contains all vertices of \(\mathcal{D}\)._  
Proof: Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Assume that \(\mathcal{WM}\) has only two solutions. Lemma 1 makes sure that the solutions are \(WW\) and \(BB\). Assume that our goal is not true; i.e., there is a cycle \(C=(a_{1},a_{2},\ldots,a_{k})\), which has no exit point and does not contain all vertices of \(\mathcal{D}\). We show that this assumption leads to a contradiction. Let us construct the following assignment: \(\{a_{1},\ldots,a_{k},\
eg b_{1},\ldots\
eg b_{m}\}\), where \(\{b_{1},b_{2},\ldots,b_{m}\}=\mathcal{V}\setminus C\), where \(\mathcal{V}\) is the set vertices of \(\mathcal{D}\). Since \(C\) has no exit point, there is no corresponding clause generated by \(CycleRep\). Since there is no clause which would falsify the constructed assignment, this is a solution of \(\mathcal{WM}\). However, this contradicts the assumption that \(\mathcal{WM}\) has only two solutions--namely, \(WW\) and \(BB\). Thus, our original statement is true. The next lemma states that a black and white SAT problem may not contain pure literals. Lemma 3: _If \(\mathcal{S}\) is a black and white SAT problem, then it contains no pure literal._  
Proof: Assume \(\mathcal{S}\) is a black and white SAT problem. Then, by definition of a black and white SAT problem, we know that \(\mathcal{S}\) has only two solutions, \(WW\) and \(BB\). Since there is no other solution of \(\mathcal{S}\) and \(\
eg WW=BB\), we obtain that \(\mathcal{S}\) may not contain a pure literal. The next lemma states that if we have a complete graph, then its weak model is a black and white SAT problem. This result is somehow natural, since the weak model of a complete graph is the biggest possible that we can generate and the weak model always has at least two solutions. **Lemma 4**: _If \(\mathcal{D}\) is a complete communication graph, and \(\mathcal{WM}\) is the weak model of \(\mathcal{D}\), then \(\mathcal{WM}\) is a black and white SAT problem._  
Assume \(\mathcal{D}\) is a complete communication graph. Assume \(\mathcal{WM}\) is the weak model of \(\mathcal{D}\). Since \(\mathcal{D}\) is complete, for any vertex \(a\) we have that \(OutE(a)\) contains all other vertices, so \(NodeRep\) contains all full-length clauses with one negative literal. Since any two vertices create a cycle where the exit points are the rest of the vertices, \(CycleRep\) contains all full-length clauses with two negative literals.