16.4.2.6. Case 6: A Degree-\(\boldsymbol{3}\) Vertex Adjacent to a Degree-\(\boldsymbol{4}\) Vertex

In this case, there exists an edge \((u,v)\) such that \(\deg(u) = 3\) and \(\deg(v) = 4\). Let \(w\) and \(x\) be the other two neighbours of \(u\). Once again, we distinguish three subcases (see Figure 16.6).

Figure 16.6: Coming soon!

Case 6.1: \(\boldsymbol{u}\) is Part of a Triangle

In this case, we assume w.l.o.g, that the triangle has vertices \(u\), \(v\), and \(w\). (This is not a loss of generality because we do not use the degrees of \(v\) and \(w\) in analyzing this case.) Consider an optimal vertex cover \(C\) of \(G\).

• If \(u \notin C\), then \(N(u) \subseteq C\).

• If \(x \notin C\), then \(N(x) \subseteq C\).

• If \(u \in C\) and \(x \in C\), then observe that \(v \in C\) or \(w \in C\) because the edge \((v,w)\) must be covered. Thus, the set \(C' = C \setminus \{u\} \cup \{v,w,x\}\) satisfies \(|C'| \le |C|\). It is a vertex cover of \(G\) because only edges incident to \(u\) are uncovered by removing \(u\) and adding \({v,w,x}\) to \(C'\) covers these edges. Thus, \(G\) has an optimal vertex cover \(C' \supseteq N(u)\) in this case.

This shows that \((G,k)\) is a yes-instance if and only if \((G - N[u],k - |N(u)|)\) or \((G - N[x], k - |N(x)|)\) is and the algorithm makes two recursive calls on these instances. Since every vertex in \(G\) has degree \(3\) or \(4\), we have \(|N(u)| = 3\) and \(|N(x)| \ge 3\). Thus, this case has the branching vector \((3,3)\), which gives a branching number no greater than 1.26.

Case 6.2: \(\boldsymbol{u}\) is Part of a \(\boldsymbol{4}\)-Cycle

If \(u\) is part of a \(4\)-cycle, this \(4\)-cycle includes \(u\) and two of \(u\)'s neighbours, say \(v\) and \(w\). (Again, we will not use the degree of \(v\) or \(w\) in the argument, so this is not a loss of generality.) If Case 6.1 does not apply, then the fourth vertex \(z\) in this cycle cannot be \(x\). Again, consider an optimal vertex cover \(C\) of \(G\).

• If \(u \notin C\), then \(N(u) \subseteq C\).

• If \(u \in C\) and \(z \notin C\), then \({v,w} \subseteq C\) because the two edges \((v,z)\) and \((w,z)\) that are part of the \(4\)-cycle \((u,v,z,w)\) must be covered. Thus, the set \(C' = C \setminus {u} \cup {v,w,x}\) has size \(|C'| \le |C|\) and is a vertex cover because every edge uncovered by the removal of \(u\) is covered by the addition of \({v,w,x}\).

This shows that there exists an optimal vertex cover \(C\) of \(G\) such that either \(N(u) = {v,w,x} \subseteq C\) or \({u,z} \subseteq C\). Thus, \((G,k)\) is a yes-instance if and only if \((G - N[u], k - |N(u)|)\) is a yes-instance or \((G - {u,z}, k-2)\) is. The algorithm makes two recursive calls on these two instances. Since \(|N(u)| = 3\), this case has the branching vector \((3,2)\) and thus branching number less than 1.33.

Case 6.3: \(\boldsymbol{u}\) is not Part of a Triangle nor of a \(\boldsymbol{4}\)-Cycle

If \(u\) is not part of a triangle nor of a \(4\)-cycle, then there are four possibilities for an optimal vertex cover \(C\) of \(G\):

• If \(u \notin C\), then \(N(u) \subseteq C\).

• If \(v \notin C\), then \(N(v) \subseteq C\).

• If \(u \in C\), \(v \in C\), and \(w, x \notin C\), then \(\{v\} \cup N(w) \cup N(x) \subseteq C\).

• If \(u \in C\), \(v \in C\), and \(\{w,x\} \cap C \ne \emptyset\), then the set \(C' = C \setminus \{u\} \cup \{v,w,x\}\) satisfies \(|C'| \le |C|\) and is a vertex cover because every edge uncovered by removing \(u\) from the vertex cover is covered by adding its neighbours \(v\), \(w\), and \(x\).

This shows that there exists an optimal vertex cover \(C\) of \(G\) such that \(N(u) \subseteq C\), \(N(v) \subseteq C\) or \({v} \cup N(w) \cup N(x) \subseteq C\). Thus, the algorithm makes three recursive calls on the instances \((G - N[u], k - |N(u)|)\), \((G - N[v], k - |N(v)|)\), and \((G - (N[u] \cup N[w] \cup N[x]), k - |{v} \cup N(w) \cup N(x)|)\). Since \(u\) is not part of a \(4\)-cycle, we have \(N(w) \cap N(x) = {u}\). Since \(u\) is not part of a triangle, we have \(v \notin N(w) \cup N(x)\). Thus, since every vertex in \(G\) has degree at least \(3\), \(|{v} \cup N(w) \cup N(x)| = 1 + \deg(w) + \deg(x) - 1 = \deg(w) + \deg(x) \ge 6\). Since \(|N(u)| = 3\) and \(|N(v)| = 4\), this shows that this case has the branching vector \((3,4,6)\), which gives a branching number less than \(1.31\).