17.2.1. Extending Independent Sets

If \(F\) is an independent set, then \(G[F]\) is clearly a forest (without edges). If \(F\) is not an independent set but \(G[F]\) is a forest, then the following lemma allows us to reduce finding an element in \(\mathcal{M}_G(F)\) to the case when \(F\) is an independent set.

Assume that \(F\) is not an independent set but \(G[F]\) is a forest, and let \(T \subseteq F\) be a maximal subset such that \(G[T]\) is connected. Then let \(G' = G|_{T \rightarrow v_T}\) be the graph obtained from \(G\) as follows:

• We start by removing all vertices (and their incident edges) that are adjacent to at least two vertices in \(T\).

• We remove all vertices in \(T\) and add a new vertex \(v_T\).

• For every vertex \(v \notin T\) that has exactly one neighbour in \(T\), we add an edge \((v, v_T)\).

Another way of describing this construction is that we remove all vertices with at least two neighbours in \(T\) and then contract \(T\) to a single vertex \(v_T\). This is illustrated in Figure 17.1.

Figure 17.1: Coming soon!

Let \(F' = F \setminus T \cup \{v_T\}\). It is easily seen that \(G'[F']\) is acyclic, so \(\mathcal{M}_{G'}(F')\) is non-empty.

Lemma 17.2: For any element \(F^* \in \mathcal{M}_{G'}(F')\), \(F^* \cup T \setminus \{v_T\} \in \mathcal{M}_G(F)\).

By this lemma, if \(F\) is not an independent set, then we can find an element in \(\mathcal{M}_G(F)\) by identifying the vertex sets \(T_1, \ldots, T_k\) of the connected components of \(G[F]\). Then we construct a sequence of graphs \(G = G_0, \ldots, G_k = G'\) and vertex sets \(F = F_0, \ldots, F_k = F'\), where \(G_i = G_{i-1}|_{T_i \rightarrow v_{T_i}}\) and \(F_i = F_{i-1} \setminus T_i \cup \{v_{T_i}\}\) for all \(1 \le i \le k\). \(F'\) is an independent set in \(G''\), and given an element \(F^* \supseteq F' \in \mathcal{M}_{G'}(F')\), we can construct elements of \(\mathcal{M}_{G_{k-1}}(F_{k-1}), \ldots, \mathcal{M}_{G_0}(F_0) = \mathcal{M}_G(F)\) by repeated application of the lemma.

Proof: To prove the lemma, we need to prove that \(G\bigl[F^* \cup T \setminus \{v_T\}\bigr]\) is a forest and that there is no larger set \(F'' \supset F\) such that \(G\bigl[F''\bigr]\) is a forest. The latter follows if we can prove that for every \(F'' \in \mathcal{M}_{G}(F)\), \(F'' \setminus T \cup \{v_T\} \subseteq V(G')\) and \(G'\bigl[F'' \setminus T \cup \{v_T\}\bigr]\) is a forest. Indeed, if \(F'' \supseteq F\) and \(|F''| > |F^* \cup T \setminus \{v_T\}|\), then \(F'' \setminus T \cup \{v_T\} \supseteq F'\) and \(|F'' \setminus T \cup \{v_T\}| = |F''| - |T| + 1 > |F^* \cup T \setminus \{v_T\}| - |T| + 1 = |F^*|\), contradicting that \(F^* \in \mathcal{M}_{G'}(F')\).

So consider any set \(F'' \supseteq F\) such that \(G[F'']\) is a forest, and let \(F''' = F'' \setminus T \cup \{v_T\}\). We need to prove that \(F''' \subseteq V(G')\) and that \(G'[F''']\) is a forest.

Let \(W = (V(G) \setminus T) \setminus V(G')\) be the set of vertices removed from \(G\) because they each have at least two neighbours in \(T\). Then \(F'' \cap W = \emptyset\). Indeed, for any vertex \(w \in W\), \(G[F \cup \{w\}]\) includes a cycle because \(w\) has two neighbours \(x\) and \(y\) in \(T\) and there exists a path from \(x\) to \(y\) in \(G[T] \subseteq G[F]\) because \(G[T]\) is connected. Thus, \(F''' = F'' \setminus T \cup \{v_T\} \subseteq V\bigl(G'\bigr)\).

To see that \(G'\bigl[F'''\bigr]\) is a forest, observe that any cycle \(C\) in \(G'\bigl[F'''\bigr]\) must include \(v_T\). Indeed, \(F''' \setminus \{v_T\} = F'' \setminus T\) and \(G'\bigl[F'' \setminus T\big] = G\bigl[F'' \setminus T\bigr]\). Thus, if \(G'\bigl[F'''\bigr]\) contains a cycle that does not include \(v_T\), it is a cycle in \(G'\bigl[F'' \setminus T\bigr] = G\bigl[F'' \setminus T\bigr] \subseteq G\bigl[F''\bigr]\), a contradiction.

So consider any cycle \(C\) in \(G'\bigl[F'''\bigr]\), which must include \(v_T\). Let \(u\) and \(w\) be the two neighbours of \(v_T\) in \(C\). Then \(u\) and \(w\) have neighbours \(u'\) and \(w'\) in \(T\). By replacing \(v_T\) with a path from \(u'\) to \(w'\) in \(T\), we obtain a cycle in \(G[F'']\), again a contradiction. Thus, \(G'[F''']\) is a forest, as claimed.

A completely analogous argument shows that \(G[F^* \cup T \setminus {v_T}]\) is a forest. ▨