16.4.2.2. Case 2: Degree-1 Vertices

If there exists a degree-1 vertex \(u\), let \(v\) be its only neighbour. We already observed in Section 16.3.1 that \((G, k)\) is a yes-instance if and only if \((G - \{u,v\}, k-1)\) is. Thus, the algorithm makes only one recursive call in this case.