## 4 Minimal Connected Vertex Cover Enumeration
### General Graphs
In other words, the bipartite graph \(H\) is obtained from \(G\) by contracting each connected component \(C\) in \(G[X^{\prime}]\) into a single vertex \(v_{C}\). Then, every (minimal) valid augmentation for \(X^{\prime}\) is a vertex set \(W\subseteq R\) such that \(H[L\cup W]\) is connected, and vice versa. Moreover, such a set \(W\) is also a (minimal) valid augmentation for \(L\) (in \(H\)). Hence, our subsequent discussion will be on the bipartite graph \(H\). In the remaining of this section, we assume that \(H\) is connected. Proposition 4: _Let \(W\subseteq R\) be a valid augmentation for \(L\) in \(H\). Then, \(W\) is minimal if and only if each vertex of \(W\) is a cut vertex in \(H[L\cup W]\)._  
We introduce some notations to explain our algorithm. The collection of minimal valid augmentations in \(H\) for \(L\) is denoted by \(\mathcal{S}(H,L)\). For a collection of valid augmentations \(\mathcal{A}\) in \(H\), the set of minimal valid augmentations in \(\mathcal{A}\) is denoted by \(\texttt{min}_{H,L}(\mathcal{A})\) (i.e., \(\texttt{min}_{H,L}(\mathcal{A})=\mathcal{A}\cap\mathcal{S}(H,L)\)). For a collection of sets \(\mathcal{U}=\{U_{1},\ldots,U_{l}\}\) and an element \(e,\mathcal{U}+e\) denotes \(\{U_{1}\cup\{e\},\ldots,U_{l}\cup\{e\}\}\). We extend this notation to a set of elements: For a set \(X\), \(\mathcal{U}+X\) denotes \(\{U_{1}\cup X,\ldots,U_{l}\cup X\}\). For \(X\subseteq R\), we define a bipartite graph \(H_{X}\) obtained from \(H\) by contracting each connected component \(C\) in \(H[L\cup X]\) into a single vertex \(v_{C}\). We also define  
\[L_{X}=\{v_{C}:C\text{ is a component in }H[L\cup X]\text{ containing a vertex in }L\}.\]  
Clearly, we have \(H_{\emptyset}=H\) and \(L_{\emptyset}=L\). When \(X=\{v\}\), we respectively denote \(H_{\{v\}}\) and \(L_{\{v\}}\) by \(H_{v}\) and \(L_{v}\) as shorthand notations. Lemma 3: _Let \(W\in\mathcal{S}(H,L)\). For \(W^{\prime}\subseteq W\), \(W\setminus W^{\prime}\) is a minimal valid augmentation for \(L_{W^{\prime}}\) in \(H_{W^{\prime}}\)._  
Proof: Since \(H_{W^{\prime}}[L_{W^{\prime}}\cup(W\setminus W^{\prime})]\) is obtained from \(H[L\cup W]\) by contracting each component \(C\) of \(H[L\cup W]\) containing a vertex in \(W^{\prime}\) into a single vertex \(v_{C}\), \(H_{W^{\prime}}[L_{W}\cup(W\setminus W^{\prime})]\) is connected, and hence \(W\setminus W^{\prime}\) is a valid augmentation for \(L_{W^{\prime}}\) in \(H_{W^{\prime}}\). Since \(W\in\mathcal{S}(H,L)\), by Proposition 4, each vertex in \(W\) is a cut vertex in \(H[L\cup W]\). Moreover, as \(W\) is an independent set in \(H\), all the neighbors of \(W\setminus W^{\prime}\) are preserved in \(H_{W^{\prime}}\). This implies that every vertex in \(W\setminus W^{\prime}\) is still a cut vertex in \(H_{W^{\prime}}[L_{W^{\prime}}\cup(W\setminus W^{\prime})]\). Hence, by Proposition 4, \(W\setminus W^{\prime}\) is a minimal valid augmentation for \(L_{W^{\prime}}\) in \(H_{W^{\prime}}\). Lemma 4: _Let \(X\subseteq R\). For \(W\in\mathcal{S}(H_{X},L_{X})\), \(W\cup X\) is a valid augmentation for \(L\) in \(H\)._  
Proof: We claim that there is a path between \(u\) and \(v\) in \(H[L\cup W\cup X]\) for \(u,v\in L\), which implies that \(H[L\cup W\cup X]\) is connected, as each vertex in \(W\cup X\) has a neighbor in \(H\). If \(u\) and \(v\) are contained in a single component in \(H[L\cup X]\), we have finished. Thus, we assume that \(u\) and \(v\) belong to distinct components \(C\) and \(C^{\prime}\), respectively. Since \(H_{X}[L_{X}\cup W]\) is connected, there is a path \(P_{X}\) between \(v_{C}\) and \(v_{C^{\prime}}\) in \(H_{X}[L_{X}\cup W]\). From this path \(P_{X}\), we can construct a path between \(u\) and \(v\) in \(H[L\cup W\cup X]\) by appropriately replacing a vertex \(v_{C^{\prime\prime}}\) in \(P_{X}\) with a path in component \(C^{\prime\prime}\). Hence, \(W\cup X\) is a valid augmentation for \(L\) in \(H\). Our algorithm shares the same underlying idea as [19; 39], which is described in Algorithm 1.