# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results
The same is true for any \(k=2\ldots n-1\) vertices, so \(CycleRep\) contains all full-length clauses with \(2,\ldots,n-1\) negative literals. However, \(\mathcal{WM}\) does not subsume the full-length clause with no negative literals, i.e., the white clause (\(WW\)), nor the full-length clause with \(n\) negative literals, i.e., the black clause (\(BB\)). This means that \(\mathcal{WM}\) has only two solutions, the white and the black assignment; i.e., \(\mathcal{WM}\) is a black and white SAT problem. Now comes one of our main contributions, the theorem which states that the weak model of a strongly connected graph is a black and white SAT problem, which means that if the graph is strongly connected, then the weak model has the same power as the strong model. Since the proof is rather technical, we give also a high-level proof of it. From left to right we prove the theorem in a constructive way: Let us have a sequence of vertices which can be built by Lemma 3 and by the construction of \(NodeRep\). Eventually we will find a cycle at the end of this sequence. Lemma 2 ensures that there is an exit point from this cycle, which either results in a bigger cycle, or in a longer sequence. Using these two steps, eventually we construct a strongly connected component. From Lemma 2 it follows that it is also maximal (otherwise there would be an exit point from it which would allow one to do the above steps); i.e., the graph is strongly connected. From right to left we use induction: We start the proof from a complete graph. We know that complete graphs are also strongly connected. As the induction step, we drop an edge from this graph such that it remains strongly connected. We assume that before the drop the weak model was black and white, which is true by Lemma 4. We show that it remains black and white also after the drop. To show this, we show that each clause in the model after the drop is a subset of some clause from the mode before the drop. Thus, the new model may not have more solutions then the old one. However, the new model has to have at least two solutions by Lemma 1. Thus, the new model is black and white. Since our graph can be constructed by dropping edges from a complete graph, which has the same set of vertices, its weak model is also black and white. **Theorem 2**: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Then \(\mathcal{WM}\) is a black and white SAT problem if and only if \(\mathcal{D}\) is strongly connected._  
Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). We show that \(\mathcal{WM}\) is a black and white SAT problem if and only if \(\mathcal{D}\) is strongly connected. (From left to right:) We assume \(\mathcal{WM}\) is a black and white SAT problem; we show by construction that \(\mathcal{D}\) is strongly connected. (R0) Let \(a_{1}\) be a vertex from \(\mathcal{D}\). Let \(j=1\). (R1) Now we have a sequence of vertices: \(a_{1},\ldots,a_{j}\). We work with its last vertex: \(a_{j}\). From Lemma 3 we know that literal \(a_{j}\) is not pure in \(\mathcal{WM}\), so \(\
eg a_{j}\) is present in \(\mathcal{WM}\). Thus, there must be a clause in \(\mathcal{WM}\) generated be \(NodeRep\) for vertex \(a_{j}\). Since \(NodeRep\) is a subset of \(CycleRep\), by Lemma 2, there is a clause \(\{\
eg a_{j},b_{1},\ldots,b_{k}\}\) in \(\mathcal{WM}\). Let \(a_{j+1}\) be a vertex from \(b_{1},\ldots,b_{k}\) such that \(a_{j+1}\) is not in \(\{a_{1},\ldots,a_{j}\}\). If this is possible, then let \(j=j+1\) and go to (R1). Note that this is not always possible because \(\mathcal{D}\) is a final graph, so eventually each vertex from \(b_{1},\ldots,b_{k}\) must be in the set \(\{a_{1},\ldots,a_{j}\}\). In this case let \(a_{j+1}\) be a vertex from \(b_{1},\ldots,b_{k}\) such that \(a_{j+1}=a_{i}\), where \(i<j\) and \(i\) is the smallest possible. This means that we have \(i\) such that \(i<j\) and \(a_{i}=a_{j+1}\); i.e., \((a_{i},\ldots,a_{j})\) is a cycle. Go to (R2).