# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results
(R2) Now we have a sequence of vertices \(a_{1},\ldots,a_{j}\), and the end of this sequence from \(a_{i}\) to \(a_{j}\) is a cycle. If \(i=1\) and the cycle contains all the vertices from \(\mathcal{D}\), then go to (R3). Otherwise, by creation of \(CycleRep\) and by Lemma 2 we know that \(\mathcal{WM}\) contains a clause \(\{\
eg a_{i},\ldots,\
eg a_{j},b_{1},\ldots,b_{m}\}\), where \(b_{1},\ldots,b_{m}\) are exit points of the cycle \((a_{i},\ldots,a_{j})\). Let \(a_{j+1}\) be a vertex from \(b_{1},\ldots,b_{m}\) such that \(a_{j+1}\) is not present 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_{m}\), such that \(a_{j+1}=a_{i^{\prime}}\) and \(i^{\prime}\) is the smallest possible. Since \(b_{1},\ldots,b_{m}\) are exit points of the cycle \((a_{i},\ldots,a_{j})\), we know that \(i^{\prime}\) is smaller than \(i\) because each vertex from \(b_{1},\ldots,b_{m}\) is different from \(a_{i},\ldots,a_{j}\). This means that we have \(i^{\prime}\) such that \(i^{\prime}<j\), and \(i^{\prime}<i\) and \(a_{i^{\prime}}=a_{j+1}\); i.e., \((a^{\prime}_{i^{\prime}},\ldots,a_{j})\) is a cycle. Let \(i=i^{\prime}\), and go to (R2). (R3) Eventually (R2) exists to (R3) because, by Lemma 2, each cycle has at least one exit point, which results in a bigger cycle, or in a longer \(a_{1},\ldots,a_{j}\) sequence of vertices. Thus, eventually the sequence \(a_{1},\ldots,a_{j}\) will contain all vertices, and eventually \(i\) will be \(1\), so eventually we will find a cycle which contains all vertices. Hence, \(\mathcal{D}\) is strongly connected. (From right to left:) We assume \(\mathcal{D}\) is strongly connected; we show by induction that \(\mathcal{WM}\) is a black and white SAT problem. Let \(H\) be the complete communication graph which has the same set of vertices as \(\mathcal{D}\). We know from Lemma 4 that the weak model of \(H\) is a black and white SAT problem. This is our induction base. It is well known that complete graphs are also strongly connected. We create \(G\) from \(H\) by deleting edges from \(H\) such that \(G\) remains strongly connected. Let \(Z\) be the weak model of \(G\). Our induction hypothesis is that \(Z\) is a black and white SAT problem. Our induction step is that we delete an edge from \(G\) such that it remains strongly connected. Let \(G^{\prime}\) be this graph. Let \(Z^{\prime}\) be the weak model of \(G^{\prime}\). We show that \(Z^{\prime}\) is a black and white SAT problem. To show this, we show that \(Z^{\prime}\geq Z\); i.e., \(Z^{\prime}\) subsumes all clauses from \(Z\). Without loss of generality let us assume that we deleted the edge from vertex \(a\) to vertex \(b\). All clauses from \(Z\) are the same as the clauses of \(Z^{\prime}\), except the ones generated by \(CycleRep\) for those cycles which contain \(a\). From those clauses let \(D=\{\
eg a_{1},\ldots,\
eg a_{k},b_{1},\ldots,b_{m}\}\) be an arbitrary but fixed one, where \((a_{1},\ldots,a_{k})\) is a cycle in \(Z\) and \(b_{1},\ldots,b_{m}\) are its exit points. We know that \(k>=1\) and \(a=a_{i}\) for some \(i\in\{1,\ldots,k\}\), and \(b\) is one of the other vertices from this clause. There are the following cases:  
* If \(b\) is one of the exit points and some other vertex from the cycle has an edge to \(b\), then \(Z^{\prime}\) contains the same clause: \(D\). * If \(b\) is one of the exit points, say \(b=b_{p}\), where \(p\in\{1,\ldots,m\}\), and no other vertex from the cycle has an edge to \(b\), then \(Z^{\prime}\) contains the clause \(\{\
eg a_{1},\ldots,\
eg a_{k},b_{1},\ldots,b_{p-1},b_{p+1},\ldots b_{m}\}\), which is a subset of \(D\).