Bounded search tree: k-Vertex cover with $\Delta(G) = 2$

Question

I am studying the book "Parametrized Algorithms" and it suggests a bounded search tree algorithm for k-Vertex Cover. Basically we look at a vertex v and say :
Either v will cover it's incident edges or it has to be it's neighbors $N(V)$ so either $v$ or $N(v)$ will end up in the cover.
That's 2 choices , we build a tree with these . The total running time is summarized by this relation :
$T(k) =T(k-1) + T(k-N(v)) + O(n)$
Considering the interesting case is $N(v) \geq 2$ then $k - N(v) \leq k-2$ so we get: $$T(k) =T(k-1) + T(k-2) + O(n)$$ Now the book says that "Vertex Cover can be solved optimally in polynomial time when the maximum degree of a graph is at most 2".
"Thus, we branch only on the vertices of degree at least 3, which immediately brings us to the following upper bound on the number of leaves in a search tree:"

Since the are no vertices with degree 3 or more how do we branch on these ? What am I missing here?

Answer 1

Once all vertices have degree $<=2$ you don't branch on them - you just apply a standard polynomial time algorithm to solve it.

Since your graph consists of a disjoint set of cycles and line graphs, the min vertex cover for components which are line graphs would be $⌊C/2⌋$ and $⌈C/2⌉$ for cycles where $C$ is the size of the component. Therefore this can be solved in $O(n+m)$ as the problem just reduces to finding the size of components within a graph.

The recurrence given is for reducing the graph to a form where all vertices have degree $<=2$ as you either remove the current vertex or remove 3 of its neighbours. Doing this repeatedly will eventually lead you to a graph where all vertices have degree $<=2$