17.2.2. Generalized Neighbours

So assume from now on that \(F\) is an independent set of \(G\). The next lemma will be used to justify two of the branching rules of the algorithm. Let \(t \in F\), and let \(v \in N(t)\). Since \(F\) is an independent set, we have \(v \in V \setminus F\). Let \(K = N(v) \cap F \setminus \{t\}\) and let \(\tilde N_t(v) = N(v) \setminus F \cup \bigcup_{u \in K} N(u) \setminus \{v\}\). We call the vertices in \(\tilde N_t(v)\) the generalized neighbours of \(v\) with respect to \(t\). This definition is illustrated in Figure 17.2.

Figure 17.2: Coming soon!

Lemma 17.3: Let \(F\) be an independent set of \(G\), let \(t \in F\), and let \(v \in N(t)\). Then there exists an element \(F^* \in \mathcal{M}_G(F)\) such that either \(v \in F^*\) or \(|F^* \cap \tilde N_t(v)| \ge 2\).

Proof: Let \(F^* \in \mathcal{M}_G(F)\). Assume that \(v \notin F^*\) and \(|F^* \cap \tilde N_t(v)| \le 1\) because otherwise the lemma holds. Then let \(F' = F^* \setminus \tilde N_t(v) \cup \{v\}\). We have \(v \in F'\) and \(|F'| \ge |F^*|\). Thus, it suffices to prove that \(G[F']\) is a forest, so \(F' \in \mathcal{M}_G(F)\).

Assume the contrary and let \(C\) be a cycle in \(G[F']\). Since \(G[F^*]\) is a forest, so is \(G[F^* \setminus \tilde N_t(v)]\). Thus, \(C\) must include \(v\). Let \(u\) and \(w\) be \(v\)'s neighbours in \(C\). Since \(u \ne w\), we can assume w.l.o.g. that \(u \ne t\).

If \(u \notin F\), then \(u \in \tilde N_t(v)\) because \(u \in N(v) \setminus F\). Since \(F' \cap \tilde N_t(v) = \emptyset\) and \(V(C) \subseteq F'\), this is a contradiction.

If \(u \in F\), then \(u \in K\) because \(u \ne t\). Let \(x\) be \(u\)'s other neighbour in \(C\). Then \(x \in N(u) \setminus \{v\}\), that is, \(x \in \tilde N_t(v)\), again a contradiction. This shows that \(G[F']\) is a forest and thus proves the lemma. ▨