5 Connected Dominating Set and Max Leaf Spanning Tree
This section prepares the applications of Sections 6, 7, 8 and 10: the equivalence of Max Leaf Spanning Tree and Connected Dominating Set (Lemma 5.1), a vertex-weighted directed Steiner tree computation by inclusion–exclusion (Lemma 5.3), the Steiner extension algorithm built on it, whose running-time exponent is the number of terminals that the sample leaves (Corollary 5.8), and the mean bound on this running-time exponent (Lemma 5.11).
All graphs are finite, simple and undirected. Throughout, \(G\) is a graph with vertex set \(V=V(G)\) and \(n=|V|\) vertices; when \(G\) is fixed we write \(N(v)\), \(N[v]\), \(N[X]=\bigcup_{x\in X}N[x]\) and \(N(X)=N[X]\setminus X\) for \(N_G(v)\), \(N_G[v]\), \(N_G[X]\) and \(N_G(X)\). For a subgraph \(F\subseteq G\) we keep the subscript: \(N_F(v)\), \(N_F[X]\) and \(d_F(v)\) are neighborhoods and degrees in \(F\). For a graph, \(\operatorname{comp}(\cdot)\) denotes the number of its connected components; in particular \(\operatorname{comp}(G[\emptyset])=0\). A connected dominating set of \(G\) is a nonempty set \(S\subseteq V\) with \(N[S]=V\) such that \(G[S]\) is connected; a graph that has one is connected, and for a connected graph \(G\) we write \(\gamma_{\mathrm{c}}(G)\) for the minimum size of a connected dominating set. Connected Dominating Set asks for \(\gamma_{\mathrm{c}}(G)\), and Max Leaf Spanning Tree (MaxLeaf) asks for the maximum number of leaves of a spanning tree of a connected graph \(G\).
The following equivalence of the two problems is folklore; it is stated, for example, by Caro, West and Yuster (Caro, West, and Yuster 2000), by Fomin, Grandoni and Kratsch (Fomin, Grandoni, and Kratsch 2008), by (Fernau et al. 2011, sec. 1) and by Abu-Khzam, Mouawad and Liedloff (Abu-Khzam, Mouawad, and Liedloff 2011, sec. 1). We include its short proof because the construction in the second half of the proof is reused for the mean bound later in this section.
Lemma 5.1 (Max leaf and connected domination). Let \(G\) be a connected graph with \(n\) vertices. If \(n\ge3\), the maximum number of leaves of a spanning tree of \(G\) equals \(n-\gamma_{\mathrm{c}}(G)\), and a spanning tree with at least \(n-|S|\) leaves can be computed in polynomial time from any connected dominating set \(S\). If \(n\le2\), the only spanning tree of \(G\) is \(G\) itself, with no leaf if \(n=1\) and two leaves if \(n=2\).
Lean, partial: maxLeaf_eq, spanningTree_of_CDS, maxLeaf_small (formalisation)
Proof. For \(n\le2\) the claim is immediate, as a connected graph on at most two vertices is a tree. Let \(n\ge3\), let \(F\) be a spanning tree of \(G\) and let \(\operatorname{leaves}(F)\) be its set of leaves. Since \(n\ge3\), two leaves of \(F\) are never adjacent in \(F\) (they would form a component \(K_2\) of \(F\)), so the set \(S=V\setminus\operatorname{leaves}(F)\) of non-leaves is nonempty and contains the neighbor in \(F\) of every leaf; hence \(N[S]=V\). Deleting leaves from a tree leaves a tree, so \(F-\operatorname{leaves}(F)\) is a spanning tree of \(G[S]\) and \(G[S]\) is connected. Thus \(S\) is a connected dominating set and \(|\operatorname{leaves}(F)|=n-|S|\le n-\gamma_{\mathrm{c}}(G)\).
Conversely, let \(S\) be a connected dominating set. Take a spanning tree of \(G[S]\) and attach every vertex of \(V\setminus S\) by one edge to a neighbor in \(S\), which exists because \(N[S]=V\). The result is a spanning tree of \(G\) in which every vertex of \(V\setminus S\) is a leaf, so it has at least \(n-|S|\) leaves, and it is computed in polynomial time. With \(|S|=\gamma_{\mathrm{c}}(G)\) this gives the reverse inequality. ∎
All algorithms of Sections 6, 7, 8 and 10 and of Section 12 run, for \(s=1,\dots,n\) in turn, a procedure that rejects \(s\) if no solution of size at most \(s\) exists and accepts the optimum size (with probability bounded away from \(0\), for the randomized ones), and output the first accepted \(s\). The following lemma records what this wrapper needs from the inner procedure; it is stated for an arbitrary implicit set system (Definition 3.1).
Lemma 5.2 (First accepted size). Let \(\Phi\) be an implicit set system and let \(I\) be an instance of \(\Phi\) with a universe of \(n\) elements whose family \(\mathcal{F}_I\) of solutions is nonempty and does not contain the empty set; let \(\operatorname{opt}(I)\in\{1,\dots,n\}\) be the least size of a solution. Let \(\mathrm{Dec}\) be a procedure which, on input \((I,s)\) with \(1\le s\le n\), runs in time \(T\) and space \(\mathrm{Sp}\) and rejects if \(\mathcal{F}_I\) contains no set of size at most \(s\). Then running \(\mathrm{Dec}\) on \((I,1),(I,2),\dots,(I,n)\) and outputting the first accepted \(s\), or \(n\) if none is accepted, runs in time \(nT\) and space \(\mathrm{Sp}\) and never outputs a value below \(\operatorname{opt}(I)\); if \(\mathrm{Dec}\) accepts \((I,\operatorname{opt}(I))\) with probability at least \(p\), the output is \(\operatorname{opt}(I)\) with probability at least \(p\) (deterministic form: \(p=1\)). For \(\Phi_{\mathrm{CDS}}\) (Definition 5.7), a connected graph \(G\) and \(\operatorname{opt}(G)=\gamma_{\mathrm{c}}(G)\), the same procedure solves Max Leaf Spanning Tree within the same bounds, by Lemma 5.1, where graphs with \(n\le2\) vertices are handled directly in constant time.
Lean, partial: first_accepted (formalisation)
Proof. The time and space bounds are clear. An accepted \(s\) satisfies \(s\ge\operatorname{opt}(I)\), and the default output \(n\) satisfies \(n\ge\operatorname{opt}(I)\) because every solution is a subset of the universe; so the output is never below \(\operatorname{opt}(I)\). If the run on \((I,\operatorname{opt}(I))\) accepts, which happens with probability at least \(p\), then, as no smaller \(s\) is ever accepted, the output is \(\operatorname{opt}(I)\). For Max Leaf Spanning Tree, output \(n-\gamma_{\mathrm{c}}(G)\) leaves for \(n\ge3\) by Lemma 5.1; for \(n\le2\), output \(0\) if \(n=1\) and \(2\) if \(n=2\) without running \(\mathrm{Dec}\), which is correct by the last sentence of Lemma 5.1. ∎
5.1 Vertex-weighted directed Steiner trees
The extension algorithm of Section 5.2, the variants of Section 12 and Directed Steiner Tree in Section 12.5 all use one Steiner computation, on a digraph with vertex weights. This subsection states it, Lemma 5.3; its proof is in Appendix D.3.
Let \(\vec G\) be a digraph (finite, without loops or parallel arcs) with \(n\) vertices, let \(r\in V(\vec G)\) be a root, let \(K\subseteq V(\vec G)\setminus\{r\}\) be a set of terminals, and let \(\varphi\colon V(\vec G)\to\{0,1,\dots,\varphi_{\max}\}\) be vertex weights; zero weights are allowed. A set \(D\subseteq V(\vec G)\setminus(\{r\}\cup K)\) is feasible if every terminal is reachable from \(r\) in \(\vec G[\{r\}\cup K\cup D]\), and we put \[\operatorname{OPT}_\varphi(\vec G,r,K)=\min\{\varphi(D):D\text{ feasible}\},\] with \(\min\emptyset=\infty\). Equivalently, \(\operatorname{OPT}_\varphi(\vec G,r,K)\) is the least weight of the non-root, non-terminal vertices of an out-tree of \(\vec G\) rooted at \(r\) that contains \(K\). The weights of the root and of the terminals play no role.
Lemma 5.3 (Vertex-weighted directed Steiner tree). For \(\vec G\), \(n\), \(r\), \(K\) and \(\varphi\) as above, \(\operatorname{OPT}_\varphi(\vec G,r,K)\) can be computed deterministically in time \(2^{|K|}(n+\varphi_{\max})^{O(1)}\) and space \((n+\varphi_{\max})^{O(1)}\).
Lean, partial: steinerAlg_eq, bIE_count, bw_count, bw_mem, bw_zero, bw_pos, feasible_of_walk, walk_of_feasible (formalisation)
The method is Nederlof’s (Nederlof 2013): count, by inclusion–exclusion over the terminals, the branching walks from the root that visit every terminal, and read the optimum off the least length at which this count is nonzero. Nederlof states it for undirected graphs with edge weights; Lokshtanov and Nederlof obtain the same bound, \(2^{|K|}\) times a factor polynomial in \(n\) and in the largest edge weight, from the Dreyfus–Wagner recurrence (Lokshtanov and Nederlof 2010 Theorem 6.3), and (Fomin et al. 2019) remove the dependence on the weights at the price of a larger base, in time \(O(7.97^{|K|}n^4\log W)\) and polynomial space for edge weights at most \(W\). Two changes give the lemma: arcs are used only in their own direction, and the weight of a vertex, multiplied by \(n\), is added to the length of every arc that enters it, so that one unit of weight contributes more to a length than all arcs of an out-tree together. The directed case is not new: (Jones et al. 2017 Lemma 3.5) state it for a minimum-size set of non-terminals and attribute it to Nederlof and to (Misra et al. 2012), who prove it for Directed Steiner Out-Tree, with the number of vertices of the out-tree as the objective; the length encoding of vertex weights is a routine device. We regard the lemma as folklore and include a proof (Appendix D.3) because we need vertex weights, including zero weights, on a digraph.
5.2 Red–blue states and the Steiner encoding
Abu-Khzam, Mouawad and Liedloff (Abu-Khzam, Mouawad, and Liedloff 2011) solve Connected Dominating Set by reducing it to a connected red–blue domination problem, which they finish with a Steiner tree computation. We use their formulation, extended by dominating components, the connected pieces of a partial solution, which the encoding contracts to single vertices.
Definition 5.4 (State). A state of a graph \(G\) is a triple \(J=(\mathcal{D},B,R)\) in which \(\mathcal{D}\) is a family of pairwise disjoint nonempty vertex sets, each inducing a connected subgraph of \(G\), with no edge of \(G\) between two distinct members, and, writing \(V(\mathcal{D})=\bigcup_{C\in\mathcal{D}}C\), the sets \(B\) and \(R\) satisfy \(B\subseteq V\setminus V(\mathcal{D})\) and \(R\subseteq V\setminus N[V(\mathcal{D})]\). The vertices in \(B\) are blue (still available), those in \(R\) are red (still to be dominated), and the members of \(\mathcal{D}\) are the dominating components. The solutions of \(J\) are the sets \[Y\subseteq B\quad\text{with}\quad R\subseteq N[Y],\quad G[V(\mathcal{D})\cup Y]\text{ connected and}\quad V(\mathcal{D})\cup Y\neq\emptyset,\] and \(\operatorname{OPT}(J)\) is the minimum size of a solution (\(\operatorname{OPT}(J)=\infty\) if there is none). The terminals of \(J\) are its red vertices and its dominating components; their set is \(\mathrm{T}(J)=R\cup\mathcal{D}\), so \(|\mathrm{T}(J)|=|R|+|\mathcal{D}|\).
The initial state \(J_0=(\emptyset,V,V)\) has the connected dominating sets of \(G\) as its solutions, so \(\operatorname{OPT}(J_0)=\gamma_{\mathrm{c}}(G)\) for connected \(G\). For a nonempty set \(X\subseteq V\) let \(\mathcal{D}_X\) be the family of vertex sets of the components of \(G[X]\), and put \[\tag{12} J_X=\bigl(\mathcal{D}_X,\;V\setminus X,\;V\setminus N[X]\bigr),\] and \(J_\emptyset=J_0\). This is a state: the components of \(G[X]\) are disjoint, connected and pairwise non-adjacent, \(V(\mathcal{D}_X)=X\), and \(V\setminus N[X]\) avoids \(N[X]\). Unwinding the definition shows that the solutions of \(J_X\) are exactly the sets \(Y\subseteq V\setminus X\) for which \(X\cup Y\) is a connected dominating set (for \(X\neq\emptyset\) use \(N[X\cup Y]=N[X]\cup N[Y]\); for \(X=\emptyset\) this is the statement about \(J_0\)). The number of terminals is \[\tag{13} |\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\qquad\text{for every }X\subseteq V,\] including \(X=\emptyset\), where both sides equal \(n\). Since \(\operatorname{comp}(G[X])\le|X|\le|N[X]|\), this is an integer in \(\{0,\dots,n\}\); if \(X\) is a connected dominating set, then \(|\mathrm{T}(J_X)|=1\).
The Steiner encoding turns a state into an instance of the directed Steiner problem of Section 5.1. Adjacencies among blue vertices and dominating components become pairs of opposite arcs, and each red vertex becomes a sink that can be entered only from a blue vertex dominating it, so that red terminals are leaves of every out-tree. Abu-Khzam, Mouawad and Liedloff (Abu-Khzam, Mouawad, and Liedloff 2011 Lemma 2) use an undirected encoding instead, in which heavy edge weights force the red terminals to be leaves, and solve it with Nederlof’s algorithm (Nederlof 2013); this is the classical route, and the directed encoding needs no heavy weights. We allow weights on the blue vertices, which Section 12.2 uses; for the unweighted problem all weights are \(1\).
Definition 5.5 (Directed Steiner encoding). For a state \(J=(\mathcal{D},B,R)\) of \(G\) let \(\vec G_J\) be the digraph with a vertex \(\hat C\) for every \(C\in\mathcal{D}\), a vertex \(\hat b\) for every \(b\in B\) and a vertex \(\check r\) for every \(r\in R\) (a red vertex \(r\) may lie in \(B\), and then \(\hat r\) and \(\check r\) are different vertices), with the following arcs:
\(\hat b\hat b'\) and \(\hat b'\hat b\) for every edge \(bb'\) of \(G\) with \(b,b'\in B\);
\(\hat C\hat b\) and \(\hat b\hat C\) for every \(C\in\mathcal{D}\) and every \(b\in N(C)\cap B\);
\(\hat b\check r\) for every \(r\in R\) and every \(b\in N[r]\cap B\).
For weights \(\varphi\colon B\to\{0,1,\dots,\varphi_{\max}\}\) let \(\operatorname{OPT}_\varphi(J)\) be the minimum of \(\varphi(Y)\) over the solutions \(Y\) of \(J\) (\(\infty\) if there is none), and give \(\hat b\) the weight \(\varphi(b)\) and every \(\hat C\) and \(\check r\) the weight \(0\). With \(\varphi\equiv1\), \(\operatorname{OPT}_\varphi(J)=\operatorname{OPT}(J)\).
The members of \(\mathcal{D}\) are disjoint nonempty subsets of \(V\setminus B\), so \(|\mathcal{D}|+|B|\le n\) and \(\vec G_J\) has at most \(2n\) vertices. The vertices of \(\check R=\{\check r:r\in R\}\) have no outgoing arcs. The proofs of the next lemma and of Corollary 5.8 are in Appendix D.3; the first turns solutions of a state into feasible sets of its encoding, and back, and the second is the first with unit weights.
Lemma 5.6 (Directed Steiner encoding). Let \(J=(\mathcal{D},B,R)\) be a state of an \(n\)-vertex graph \(G\) and \(\varphi\colon B\to\{0,1,\dots,\varphi_{\max}\}\). If \(C_1\in\mathcal{D}\), then \(\operatorname{OPT}_\varphi(J)=\operatorname{OPT}_\varphi(\vec G_J,\hat C_1,K_1)\) for \(K_1=\{\hat C:C\in\mathcal{D}\setminus\{C_1\}\}\cup\check R\). Consequently, for every state \(J\) of \(G\), \(\operatorname{OPT}_\varphi(J)\) can be computed deterministically in time \(2^{|\mathrm{T}(J)|}(n+\varphi_{\max})^{O(1)}\) and space \((n+\varphi_{\max})^{O(1)}\).
Lean, partial: optSt_eq_optDir, isState_Jb, optSt_eq_inf_Jb, stateAlg_eq (formalisation)
The extension algorithm used in all the applications is this computation with unit weights.
Definition 5.7 (Set system and extension algorithm). Let \(\Phi_{\mathrm{CDS}}\) be the implicit set system whose instances are graphs \(G\), with universe \(V(G)\) and with the connected dominating sets of \(G\) as solutions. Let \(\mathcal{A}_{\mathrm{St}}\) be the algorithm that on input \((G,X,k)\) rejects at once if \(k<|X|\), and otherwise computes \(\operatorname{OPT}(J_X)\) and accepts if and only if \(\operatorname{OPT}(J_X)\le k-|X|\).
Corollary 5.8 (Steiner extension). For every state \(J\) of an \(n\)-vertex graph, \(\operatorname{OPT}(J)\) can be computed deterministically in time \(2^{|\mathrm{T}(J)|}n^{O(1)}\) and polynomial space. Consequently, the algorithm \(\mathcal{A}_{\mathrm{St}}\) of Definition 5.7 solves \(\Phi_{\mathrm{CDS}}\)-Extension in polynomial space, and \[g(G,X,k)=|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\] is a running-time exponent for it in the sense of Definition 3.2, with values in \(\{0,\dots,n\}\).
Lean, partial: aSt_iff_ext, aSt_iff_extYes, not_aSt_of_lt, isSol_JX_iff, isState_JX, terminals_JX, optSt_J0 (formalisation)
This running-time exponent does not depend on the size bound \(k\). For a fixed graph \(G\) and target size \(k\), the shorthand of Definition 3.2 therefore reads \(g(X)=g(G,X,k)=|\mathrm{T}(J_X)|\), and the later sections use it in this form.
The running-time exponent depends on the sample itself, not only on its size, and adding a vertex to a sample need not reduce it: if \(x\notin X\) has \(N[x]\subseteq N[X]\) and is adjacent to exactly one component of \(G[X]\), then \(|\mathrm{T}(J_{X\cup\{x\}})|=|\mathrm{T}(J_X)|\). So product-form running times cannot credit a sampled vertex with a guaranteed reduction (Section 4); the mean number of terminals, however, does decrease with the sample size, as we show next.
5.3 Sampling inside a connected dominating set
The main result of this subsection is the mean bound of Lemma 5.11. It follows from a pointwise inequality for trees, applied to a spanning tree of \(G\) in which the vertices outside the solution are leaves.
For a tree \(F\) and a set \(X\subseteq V(F)\), let \(F\{X\}\) denote the subgraph of \(F\) with vertex set \(N_F[X]\) and the edges of \(F\) with at least one end in \(X\). It records how the components of \(F[X]\) are joined to the neighbors of \(X\); the inequality below is an equality exactly when it is connected.
Lemma 5.9 (Tree inequality). Let \(F\) be a tree and let \(X\subseteq V(F)\) be nonempty. Then \[|N_F[X]|-\operatorname{comp}(F[X])\ \ge\ 1+\sum_{x\in X}\bigl(d_F(x)-1\bigr),\] with equality if and only if \(F\{X\}\) is connected.
Lean, partial: tree_inequality (formalisation)
Proof. Let \(e_X\) be the number of edges of \(F[X]\) and \(e_{XY}\) the number of edges of \(F\) with exactly one end in \(X\); the other end of such an edge lies in \(Y=N_F(X)\). Then \(\sum_{x\in X}d_F(x)=2e_X+e_{XY}\), and \(\operatorname{comp}(F[X])=|X|-e_X\) because \(F[X]\) is a forest. The graph \(F\{X\}\) is a forest with \(|X|+|Y|\) vertices and \(e_X+e_{XY}\) edges, so \(e_X+e_{XY}\le|X|+|Y|-1\), with equality if and only if \(F\{X\}\) is connected. Therefore \[|N_F[X]|-\operatorname{comp}(F[X])=|Y|+e_X\ \ge\ 2e_X+e_{XY}+1-|X|=1+\sum_{x\in X}\bigl(d_F(x)-1\bigr),\] with equality exactly when \(e_X+e_{XY}=|X|+|Y|-1\). ∎
Lemma 5.10 (Pointwise form). Let \(G\) be a connected graph with \(n\ge2\) vertices and let \(S\) be a connected dominating set of \(G\). Let \(F\) be a spanning tree of \(G\) in which every vertex of \(V\setminus S\) is a leaf; one exists, by the construction in the proof of Lemma 5.1, which needs only \(n\ge2\). Put \(w(u)=d_F(u)-1\) for \(u\in S\). Then \(\sum_{u\in S}w(u)=n-2\), and for every nonempty \(X\subseteq S\), \[|N[X]|-\operatorname{comp}(G[X])\ \ge\ 1+\sum_{x\in X}w(x).\]
Lean proof: pointwise (formalisation)
Proof. The tree \(F\) has \(n-1\) edges and the \(n-|S|\) vertices outside \(S\) have degree \(1\) in \(F\), so \(\sum_{u\in S}d_F(u)=2(n-1)-(n-|S|)\) and \(\sum_{u\in S}w(u)=n-2\). For nonempty \(X\subseteq S\) we have \(N[X]\supseteq N_F[X]\) because \(F\subseteq G\), and \(\operatorname{comp}(G[X])\le\operatorname{comp}(F[X])\) because \(F[X]\) is a spanning subgraph of \(G[X]\). Now Lemma 5.9, applied to \(F\) and \(X\), gives the inequality. ∎
Averaging the pointwise form over a uniform \(t\)-subset of the solution gives the mean bound.
Lemma 5.11 (Mean number of terminals). Let \(G\) be a connected graph with \(n\ge2\) vertices, let \(S\) be a connected dominating set of \(G\) with \(|S|=s\), let \(1\le t\le s\) and let \(X\) be uniform in \(\binom St\). Then \[\mathbb{E}\bigl[|N[X]|-\operatorname{comp}(G[X])\bigr]\ \ge\ 1+\frac{t(n-2)}s, \qquad\text{equivalently}\qquad \mathbb{E}\,|\mathrm{T}(J_X)|\ \le\ n-1-\frac{t(n-2)}s .\]
Lean proof: mean_terminals (formalisation)
Proof. Take \(F\) and \(w\) as in Lemma 5.10. As \(t\ge1\), the set \(X\) is nonempty, so Lemma 5.10 applies to it. Each \(u\in S\) lies in \(X\) with probability \(t/s\), so by linearity of expectation \[\mathbb{E}\bigl[|N[X]|-\operatorname{comp}(G[X])\bigr]\ \ge\ 1+\frac ts\sum_{u\in S}w(u)=1+\frac{t(n-2)}s .\] The second form follows from (13). ∎
The assumption \(t\ge1\) of Lemma 5.11 is needed: for \(X=\emptyset\) the expectation \(\mathbb{E}[|N[X]|-\operatorname{comp}(G[X])]\) is \(0\). The bound of Lemma 5.11 cannot be improved in general:
Proposition 5.12 (Tightness for stars). Let \(S\) be a connected dominating set of a connected graph \(G\) with \(|S|=s\ge2\). Suppose that \(G[S]\) is a star \(K_{1,s-1}\) and that every vertex of \(V\setminus S\) has exactly one neighbor in \(S\) (edges between vertices of \(V\setminus S\) are allowed). Then equality holds in Lemma 5.10 for every nonempty \(X\subseteq S\), and in Lemma 5.11 for every \(1\le t\le s\).
An example for Proposition 5.12 is the star of stars: a star on \(S\) in which every vertex of \(S\) carries \(h\) pendant vertices, so that \(n=s(h+1)\).
Proof. First, the tree \(F\) of Lemma 5.10 is unique. Deleting the leaves of \(F\) that lie outside \(S\) leaves a spanning tree of \(G[S]\), which must be the star \(G[S]\) itself. If \(V\setminus S\) is nonempty, then every \(v\notin S\) is a leaf of \(F\), and its neighbor in \(F\) lies in \(S\): otherwise that neighbor is a leaf as well and \(F\) would be a single edge, whereas \(|V(F)|\ge s+1\ge3\). So \(v\) is attached to its unique neighbor in \(S\).
For \(X\subseteq S\) we have \(G[X]=F[X]\), and \(N[X]=N_F[X]\) because the only edges of \(G\) between \(S\) and \(V\setminus S\) are edges of \(F\). So equality in Lemma 5.10 is equality in Lemma 5.9, and it remains to show that \(F\{X\}\) is connected for nonempty \(X\subseteq S\). Let \(z\) be the center of the star. If \(z\in X\), then \(F[X]\) is connected, as every other vertex of \(X\) is adjacent to \(z\), and every vertex of \(N_F(X)\) is joined to \(X\) by an edge of \(F\{X\}\). If \(z\notin X\), then the vertices of \(X\) are all adjacent to \(z\in N_F(X)\), and every other vertex of \(N_F(X)\) lies outside \(S\) and is adjacent to one of them. In both cases \(F\{X\}\) is connected. Equality in Lemma 5.11 follows, because its proof uses only Lemma 5.10 and linearity of expectation. ∎