## 3 Independent Set
### Correctness  
**Lemma 3.1**.: _Algorithm 2 always returns a maximal independent set 1._  
Proof.: This is easy to see, since each vertex deleted from \(U\) is adjacent to a vertex put in \(I\).  
**Lemma 3.2**.: _If Algorithm 2 returns \(I\), then \(|I|\geq s(G)\)._  
Proof.: If \(G\
otin\mathcal{GS}^{+}\), then the statement holds, because \(s(G)=0\). From now on assume that \(G\in\mathcal{GS}^{+}\). We argue by induction on \(v(G)\). It is trivial to see that the lemma holds for \(v(G)=1\). Let \(v(G)>1\) and assume that the lemma holds for smaller graphs. If \(G\) is complete, then \(|I|=1=s(G)\).  
Fix an arbitrary unipolar representation \(R\) of \(G\). We show that \(|I|\geq s(R,G)\). If \(G\) is not complete, the algorithm selects two non-adjacent vertices \(u\) and \(v\). The vertices \(u\) and \(v\) are either in different side cliques or one of them is in the central clique and the other is in a side clique.  
We start with the case when \(u\) and \(v\) are contained in side cliques. After inspecting their neighbourhoods, the algorithm removes from \(U\) either one or both of them along with theirneighbourhood. Suppose that it removes \(r\) of them, where \(r\) is \(1\) or \(2\). Let \(G^{\prime}\) and \(R^{\prime}\) be the graph and the representation induced by the remaining vertices. By the induction hypothesis, if \(I^{\prime}\) is the recursively retrieved set, then \(|I^{\prime}|\geq s(R^{\prime},G^{\prime})\). Let \(I\) be the independent set returned at the end of the algorithm, so that \(|I^{\prime}|+r=|I|\). Both \(u\) and \(v\) see all the vertices in their corresponding side clique, and see no vertices from different side cliques, so after removing \(r\) of them with their neighbours, the number of side cliques in the representation decreases by precisely \(r\), and hence \(s(R,G)=s(R^{\prime},G^{\prime})+r\). Now \(|I|=|I^{\prime}|+r\geq s(R^{\prime},G^{\prime})+r=s(R,G)\).  
Now w.l.o.g. assume that \(u\) belongs to a side clique and \(v\) belongs to the central clique. Then \(N^{+}(u)\) contains the side clique of \(u\) and perhaps parts of the central clique. Therefore, \(N^{+}(u)\setminus N^{+}(v)\) is a subset of the side clique of \(u\), and hence it is a clique. If \(N^{+}(v)\setminus N^{+}(u)\) is a not clique, then the algorithm continues recursively with \(G[V\setminus N^{+}(u)]\); and using the same arguments as above with \(r=1\), we guarantee correct behaviour. Now assume that \(N^{+}(v)\setminus N^{+}(u)\) is a clique. Then \(N^{+}(v)\setminus N^{+}(u)\) can intersect at most one side clique, because the vertices in different side cliques are not adjacent. In this case \(N^{+}(v)\cup N^{+}(u)\) completely covers the side clique of \(u\), completely covers the central clique, and it may intersect one additional side clique. Hence \(s(R,G)=s(R^{\prime},G^{\prime})+1\) or \(s(R,G)=s(R^{\prime},G^{\prime})+2\), where \(G^{\prime}\) and \(R^{\prime}\) are the induced graph and representation after the removal of \(N^{+}(v)\cup N^{+}(u)\). If \(I^{\prime}\) is the recursively obtained independent set, from the induction hypothesis we deduce that \(|I|=|I|^{\prime}+2\geq s(R^{\prime},G^{\prime})+2\geq s(R,G)\).