# Convert a Strongly Connected Directed Graph to
## 7 Theoretical Results
Note that the vertex sequence \(b_{1},\ldots,b_{p-1},b_{p+1},\ldots b_{m}\) contains some vertices, because \(G^{\prime}\) is a strongly connected graph; i.e., each cycle has an exit point, unless it contains all vertices. * If \(b\) is one of the other vertices of the cycle, but \(b\) is not the next vertex after \(a\) in this cycle, then \(Z^{\prime}\) contains the same clause, \(D\). * If \(b\) is one of the other vertices of the cycle, and \(b\) is the next vertex after \(a\) in this cycle, then \(a_{1},\ldots,a_{k}\) is not a cycle in \(Z^{\prime}\). If there is no other child vertex of \(a\) in \(\{a_{1},\ldots,a_{k}\}\), then the clause generated by \(NodeRep\) for \(a\) in \(G^{\prime}\) is a subset of \(D\). If there are other child vertices of \(a\) in \(\{a_{1},\ldots,a_{k}\}\), then there must be a subset of \(\{a_{1},\ldots,a_{k}\}\) which contains all other child vertices of \(a\) except \(b\), and which is a cycle in \(G^{\prime}\). The clause generated by \(CycleRep\) for this cycle in \(G^{\prime}\) is a subset of \(D\). We showed that \(Z^{\prime}\) subsumes all clauses from \(Z\). This means that \(Z^{\prime}\geq Z\); i.e., \(Z^{\prime}\) may have no other solutions than \(Z\). By our induction, hypothesis \(Z\) has only two solutions, \(BB\) and \(WW\). We know from Lemma 1 that \(BB\) and \(WW\) are solutions for \(Z^{\prime}\), because \(Z^{\prime}\) is a weak model. In addition, since \(Z^{\prime}\) may have no other solution, \(Z^{\prime}\) is a black and white SAT problem. This means that the weak model of any strongly connected communication graph is a black and white SAT problem. Hence, \(\mathcal{WM}\) is a blacked-and-white SAT problem, because \(\mathcal{D}\) is strongly connected and \(\mathcal{WM}\) is its weak model. The following lemma states that \(\mathcal{SM}\) entails \(\mathcal{WM}\) for any communication graph. This means that any solution of \(\mathcal{SM}\) is also a solution of \(\mathcal{WM}\). To show this, it is enough to show that \(\mathcal{SM}\) subsumes all clauses from \(\mathcal{WM}\). Lemma 5: _Let \(\mathcal{D}\) be a communication graph. Let \(\mathcal{SM}\) be the strong model of \(\mathcal{D}\). Let \(\mathcal{WM}\) be the weak model of \(\mathcal{D}\). Then \(\mathcal{SM}\geq\mathcal{WM}\)._  
Proof: Assume \(\mathcal{D}\) is a communication graph, \(\mathcal{SM}\) is the strong model of \(\mathcal{D}\) and \(\mathcal{WM}\) is the weak model of \(\mathcal{D}\). We show that \(\mathcal{SM}\geq\mathcal{WM}\). To show this, it is enough to show that \(\mathcal{SM}\) subsumes all clauses from \(\mathcal{WM}\). Let \(C\) is an arbitrary but fixed element of \(\mathcal{WM}\). 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})\). Since \(\mathcal{SM}\) is generated from the same graph, by its definition we know that \(\mathcal{SM}\) contains the clauses \(\{\
eg a,b_{1}\},\{\
eg a,b_{2}\},\ldots,\{\
eg a,b_{k}\}\) and all of these ones subsume \(C\). If \(C\) is an element of \(Cycles\), then, without loss of generality, we may assume that \(C=\{\
eg a_{1},\
eg a_{2},\ldots,\
eg a_{m},e_{1},e_{2},\ldots,e_{n}\}\), where \(m>0\), and \(n>0\). From the construction of \(Cycles\) we know that in \(\mathcal{D}\) there is an edge: \((d,e)\) such that \(d\) is one of the vertices from \(d_{1},d_{2},\ldots,d_{m}\), and \(e\) is one of the vertices from \(e_{1},e_{2},\ldots,e_{m}\). Since \(\mathcal{SM}\) is generated from the same graph, by its definition we know that \(\mathcal{SM}\) contains the clauses \(\{\
eg d,e\}\), which subsumes \(C\). Hence, \(\mathcal{SM}\geq\mathcal{WM}\). The following lemma states that \(\mathcal{SM}\) and \(\mathcal{WM}\) are equivalent if the represented communication graph is strongly connected or there are no branches in the graph.