## 5 Parameterization by Number of Vertex Deletions
### Degree and Color-Degree
\(\Box\)  
We now work on instances that are reduced with respect to Rule 2. Observe that in such instances every edge between two obligatory vertices has a unique color. This observation is crucial for showing the correctness of the following rules. Their aim is to remove obligatory vertices that have only obligatory neighbors. When _removing_ a vertex in these rules, we decrease \(k\) and \(n\) by one, thus the value of \(\ell\) remains the same. The correctness of the first rule is obvious. **Rule 3**. : _Let \((G,\chi)\) be an instance that is reduced with respect to Rule 2. Then, remove all connected components of \(G\) that consist of obligatory vertices only._  
The next two rules remove edges between obligatory vertices. **Rule 4**. : _Let \((G,\chi)\) be an instance that is reduced with respect to Rule 2. If \(G\) contains three obligatory vertices \(u\), \(v\), and \(w\) such that \(\{u,v\},\{v,w\}\in E\) and \(u\) has only obligatory neighbors, then remove \(\{u,v\}\) from \(G\). If \(u\) has degree zero now, then remove \(u\) from \(G\)._  
**Proof of correctness. ** Let \((G^{\prime}=(V^{\prime},E^{\prime}),\chi^{\prime})\) denote the instance that is produced by an application of the rule. We show that  
\[G\text{ has a rainbow cover of order }|V|-\ell\Leftrightarrow G^{\prime}\text{ has a rainbow cover of order }|V|^{\prime}-\ell. \tag{12}\]  
\"\(\Rightarrow\)\": If \(u\) is not removed by the rule, then this holds trivially as we remove an edge which has a unique color. Otherwise, let \(S\) be a vertex set such that \(G[S]\) is a rainbow cover. Since \(u\) is obligatory, we have \(u\in S\). The only color incident with \(u\) is \(\chi(\{u,v\})\). This color is not present in \(G^{\prime}\), so the graph \(G^{\prime}[S\setminus\{u\}]\) is a rainbow cover of \(G^{\prime}\). Since \(|V|-|V^{\prime}|=|S|-|S^{\prime}|\), the claim holds also in this case. \"\(\Leftarrow\)\": Let \(S^{\prime}\) be a set such that \(G^{\prime}[S^{\prime}]\) is a rainbow cover of \(G^{\prime}\). Since \(G\) is reduced with respect to Rule 2, \(v\) and \(w\) are connected by an edge whose color is unique. Hence, they are obligatory in \(G^{\prime}\). If the rule does not remove \(u\) from \(G\), then \(u\) is also obligatory in \(G^{\prime}\) since all its neighbors in \(G^{\prime}\) are obligatory and thus all edges incident with \(u\) in \(G^{\prime}\) have a unique color. Hence, the subgraph \(G[S^{\prime}]\) of \(G\) contains all edge colors that are present in both \(G\) and \(G^{\prime}\) plus the color \(\chi(\{u,v\})\). Thus, it is a rainbow cover of \(G\). If the rule removes the vertex \(u\), then the graph \(G[S]\) with \(S=S^{\prime}\cup\{u\}\) is a rainbow cover of \(G\): The only color that is in \(G\) but not in \(G^{\prime}\) is \(\chi(\{u,v\})\) which is present in \(G[S]\) as \(S\) contains \(u\) and \(v\). Again, the claim follows from the fact that \(|S|-|S^{\prime}|=|V|-|V^{\prime}|\). **Rule 5**. : _Let \((G,\chi)\) be an instance of Rainbow Subgraph that is reduced with respect to Rule 2. If \(G=(V,E)\) contains four obligatory vertices \(u\), \(v\), \(w\), and \(x\) such that \(\{u,v\}\in E\) and \(\{w,x\}\in E\) and \(u\) and \(x\) have only obligatory neighbors, then do the following. Remove \(\{w,x\}\) from \(G\). If \(v\) and \(w\) are not adjacent, then insert \(\{v,w\}\) and assign it a unique color. If \(x\) has now degree zero, then remove \(x\) from \(G\)._  
Proof of correctness. : Let \((G^{\prime}=(V^{\prime},E^{\prime}),\chi^{\prime})\) denote the instance that is produced by an application of the rule. We show that  
\[G\text{ has a rainbow cover of order }|V|-\ell\Leftrightarrow G^{\prime}\text{ has a rainbow cover of order }|V|^{\prime}-\ell. \tag{13}\]  
\"\(\Rightarrow\)\": Let \(S\) be a vertex set such that \(G[S]\) is a rainbow cover. Clearly, \(\{u,v,w,x\}\subseteq S\). First, consider the case that the application of the rule does not remove \(x\).