16.4.2.5. Case 5: Regular Graphs of Degree \(\boldsymbol{3}\) or \(\boldsymbol{4}\)

If the graph is \(3\)-regular or \(4\)-regular, we pick an arbitrary vertex \(v\) and make recursive calls on the two instances \((G-v, k-1)\) and \((G-N[v], k-|N(v)|)\), which is obviously correct because either \(v \in C\) or \(N(v) \subseteq C\) for any vertex cover \(C\) of \(G\).

Similar to Case 1, we will prove in the final analysis that all applications of this case increase the running time of the algorithm by only a constant factor. This time, this is true because we will be able to argue that root-to-leaf path in the recursion tree of the algorithm includes only two applications of this case.