16.4.2.4. Case 4: Degree-2 Vertices

If there exists a degree-2 vertex \(u\) with neighbours \(v\) and \(w\), we distinguish three subcases (see Figure 16.5):

Figure 16.5: Coming soon!

Case 4.1: \(\boldsymbol{v}\) and \(\boldsymbol{w}\) Are Adjacent

If \(v\) and \(w\) are adjacent, then \(u\), \(v\), and \(w\) form a triangle in \(G\). To cover all edges in this triangle, any vertex cover \(C\) of \(G\) must contain at least two of the vertices in \(\{u, v, w\}\). If \(u \in C\), then \(C' = C \setminus \{u\} \cup \{v,w\}\) is also a vertex cover because removing \(u\) uncovers only the edges incident to \(u\), and \(v\) and \(w\) cover these edges again. Since \(|C \cap \{u,v,w\}| \ge 2\), we have \(|C'| \le |C|\), that is, \(|C'| \le k\) if \(|C| \le k\). This shows that \((G,k)\) is a yes-instance if and only if \((G - \{u,v,w\},k-2)\) is a yes-instance. Therefore, the algorithm does not branch in this case and makes only one recursive call on the input \((G - \{u,v,w\}, k-2)\).

Case 4.2: \(\boldsymbol{v}\) and \(\boldsymbol{w}\) Have Degree \(\boldsymbol{2}\) and Have the Same Neighbours

If \(N(v) = N(w) = \{u,x\}\), then consider any vertex cover \(C\) of \(G\). Since \(u\) and \(x\) cover all edges covered by \(v\) and \(w\) (and possibly more edges incident to \(x\)), \(C' = C \setminus \{v,w\} \cup \{u,x\}\) is also a vertex cover of \(G\). Since \(C\) cannot cover the cycle \(C\) unless \(\{v,w\} \subseteq C\) or \(\{u,x\} \subseteq C\), we have \(|C'| \le |C|\), that is, \(|C'| \le k\) if \(|C| \le k\). This shows that \((G,k)\) is a yes-instance if and only if \((G - \{u,v,w,x\},k-2)\) is a yes-istance. Therefore, the algorithm does not branch in this case and makes only one recursive call on the input \((G - \{u,v,w,x\}, k-2)\).

Case 4.3: \(\boldsymbol{v}\) or \(\boldsymbol{w}\) Has Degree at Least \(\boldsymbol{3}\) or \(\boldsymbol{v}\) and \(\boldsymbol{w}\) Have Different Neighbourhoods

If \(\deg(v) \ge 3\) or \(\deg(w) \ge 3\), then \(|N(v) \cup N(w)| \ge 3\). If \(\deg(v) = 2\) and \(\deg(w) = 2\) but \(N(v) \ne N(w)\), then \(v\) and \(w\) have exactly one common neighbour, namely \(u\). Thus, \(|N(v) \cup N(w)| = \deg(v) + \deg(w) - 1 = 3\).

Now consider any vertex cover \(C\) of \(G\). We distinguish three cases:

• In the first case, \(v, w \in C\), that is, \(N(u) \subseteq C\).

• In the second case, \(v, w \notin C\). This implies that \(N(v) \cup N(w) \subseteq C\) because all edges incident to \(v\) or \(w\) must be covered.

• In the third case, w.l.o.g., \(v \in C\) and \(w \notin C\). Since \(w \notin C\), we must have \(u \in C\) because the edge \((u,w)\) must be covered. The set \(C' = C \setminus \{u\} \cup \{w\}\) has the same size as \(C\) and is also a vertex cover of \(G\) because removing \(u\) only uncovers the edge \((u,w)\) and adding \(w\) covers this edge again. Moreover, \(N(u) \subseteq C'\).

This analysis shows that \(G\) has an optimal vertex cover \(C\) such that either \(N(u) \subseteq C\) or \(N(v) \cup N(w) \subseteq C\). Thus, \((G,k)\) is a yes-instance if and only if \((G - N[u], k-|N(u)|)\) or \((G - (N[v] \cup N[w]), k-|N(v) \cup N(w)|)\) is. Since \(|N(u)| = 2\) and, as argued above, \(|N(v) \cup N(w)| \ge 3\), this case has the branching vector \((2,3)\) and thus has a branching number no greater than 1.33.