## 4 Minimal Connected Vertex Cover Enumeration  
### Bounded-Degree Graphs  
In order to enumerate all minimal connected vertex covers in a graph, it suffices to construct a directed graph discussed in the previous section. To be more precise, let \(G\) be a connected graph with maximum degree \(\Delta\) and let \(\mathcal{S}_{\text{cvc}}\) be the collection of all minimal connected vertex covers of \(G\). Let \(X,Y\in\mathcal{S}_{\text{cvc}}\) with \(X\
eq Y\). From the minimality of \(X\) and \(Y\), there is a vertex \(v\in X\setminus Y\). As \(Y\) is a vertex cover of \(G\) not including \(v\), all the neighbors of \(v\) are included in \(Y\) (i.e., \(N(v)\subseteq Y\)). We define a vertex cover \(X^{\prime}\) of \(G\) as \(X^{\prime}\coloneqq(X\setminus\{v\})\cup N(v)\). Using the connectivity of \(G[X]\), we have the following observation:  
Proposition 3: _Each component of \(G[X^{\prime}]\) has at least one vertex of \(N(v)\)._  
This observation indicates that the number of connected components in \(G[X^{\prime}]\) is upper bounded by \(\Delta\). Lemma 1: _Let \(S\subseteq V(G)\) be an arbitrary vertex cover of \(G\) and let \(Y\) be a minimal connected vertex cover of \(G\). Suppose that each component in \(G[S]\) has at least one vertex of \(Y\). Then, there is a vertex set \(W\subseteq Y\) of at most \(q-1\) vertices such that \(G[S\cup W]\) is connected, where \(q\) is the number of connected components in \(G[S]\)._  
Proof: We prove the lemma by induction on the number of connected components \(q\) in \(G[S]\). If \(G[S]\) is connected, we have finished. Suppose otherwise. Let \(C\) and \(C^{\prime}\) be distinct components in \(G[S]\). Since both \(C\cap Y\) and \(C^{\prime}\cap Y\) are nonempty, there is a path \(P\) in \(G[Y]\) connecting \(C\cap Y\) and \(C^{\prime}\cap Y\). We choose \(C\) and \(C^{\prime}\) to minimize the length of such a path \(P\). Since \(S\) is a vertex cover of \(G\), the length of \(P\) is exactly \(2\). Let \(w\) be the (unique) internal vertex of \(P\). Applying the induction to \(S\cup\{w\}\) proves the lemma. We say that a vertex set \(W\) is a _valid augmentation_ for \(X^{\prime}\) if \(G[X^{\prime}\cup W]\) is connected. In particular, a valid augmentation \(W\) for \(X^{\prime}\) is called a \(Y\)-_valid augmentation_ for \(X^{\prime}\) if \(W\subseteq Y\). Thus, Lemma 1 ensures that there is a \(Y\)-valid augmentation \(W\) for \(X^{\prime}\) of size at most \(\Delta-1\) for any \(Y\in\mathcal{S}_{\text{cvc}}\). As \(v\in X\setminus Y\), \(N(v)\subseteq Y\), and \(W\subseteq Y\), we have  
\[|X\setminus Y|\geq|(X^{\prime}\cup\{v\})\setminus(N(v)\cup Y)|>|X^{\prime} \setminus Y|=|(X^{\prime}\cup W)\setminus Y|\geq|Z\setminus Y|,\]  
where \(Z\) is an arbitrary minimal connected vertex cover of \(G\) with \(Z\subseteq X^{\prime}\cup W\). Now, we formally define \(\mathcal{N}^{+}(X)\) for \(X\in\mathcal{S}_{\text{cvc}}\). For a connected vertex cover \(C\) of \(G\), we let \(\mu(C)\) be an arbitrary minimal connected vertex cover of \(G\) with \(\mu(C)\subseteq C\). Using Proposition 1, \(\mu(C)\) can be computed in polynomial time by greedily removing vertices from \(C\). We define  
\[\mathcal{N}^{+}(X)=\{ \mu((X\setminus\{v\})\cup N(v)\cup W):\] \[v\in X,W\text{ is a valid augmentation for }(X\setminus\{v\})\cup N(v),|W|\leq \Delta-1\},\]  
which can be computed in \(n^{\Delta+O(1)}\) time by just enumerating all valid augmentations \(W\) of size at most \(\Delta-1\). As discussed above, for each \(Y\in\mathcal{S}_{\text{cvc}}\) with \(X\
eq Y\), \(\mathcal{N}^{+}(X)\) has a minimal connected vertex cover \(Z\in\mathcal{S}_{\mathrm{cvc}}\) such that \(|X\setminus Y|>|Z\setminus Y|\). Using Theorem 1, we have the following. Theorem 4.1: _There is an \(n^{\Delta+O(1)}\)-delay enumeration algorithm for Minimal Connected Vertex Cover Enumeration._  
The running time of the algorithm in Theorem 4.1 depends, in fact, on the number of connected components in \(G[X^{\prime}]\) with \(X^{\prime}=(X\setminus\{v\})\cup N(v)\) rather than the degree of \(v\).