# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 4 Necessary and Sufficient Conditions for the Existence of a Solution  
To solve the capacity-constrained spanning problems, solutions do not always exist, neither for the minimum spanning hierarchy nor for the minimum Steiner hierarchy problem. The conditions for the existence of a minimum spanning hierarchy are presented in Section 4 in [29]. Here, we offer the conditions for the Steiner hierarchy problem. Despite the differences between the concerned node sets, an adaptation allows us to formulate  
Figure 1: Illustration of a DCMSth. similar lemmas and proofs (cf. Lemmas 2 and 4-6). The conditions are not completely identical but close in the two problems. Remember, \(V_{m}\subseteq V\) indicates the subset of nodes with degree bound \(m\). The nodes in \(V_{1}\) must be leaves in any solution and cannot be internal nodes in any spanning structure. If the graph \(G\) contains nodes in \(V_{1}\) that are not in \(M\), these nodes cannot belong to any solution and can be deleted. We let \(G^{\prime}=(V^{\prime},E^{\prime})\), the graph obtained after the suppression of nodes in \(V_{1}\setminus M\). \(V^{\prime}=V\setminus(V_{1}\setminus M)\), and \(E^{\prime}\) does not contain the adjacent edges of the deleted nodes. Graph \(G^{\prime}\) is not necessarily connected. Lemma 1: _If \(G^{\prime}\) does not contain a connected component containing all the nodes of the set \(M\), there is no hierarchy spanning \(M\) and satisfying the degree constraints._  
Proof: In a spanning hierarchy, there is a walk between any pair of nodes. If there are members of \(M\) in different connected components in \(G^{\prime}\), then some walks are missing for a spanning structure. We let \(G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})\) be the connected component in \(G^{\prime}\) that contains the node set \(M\). Remember, the subset \(V^{\prime\prime}_{i}\) is the subset of nodes with degree bound \(i\) in \(G^{\prime\prime}\), especially \(V^{\prime\prime}_{1}\subseteq M\). Lemma 2: _If \(V^{\prime\prime}_{1}\) contains a separator (removing a separator makes a graph disconnected) such that the nodes in \(M\) are separated into two or more sub-graphs, there is no hierarchy spanning \(M\) and satisfying the degree constraints._  
Proof: We let \(A\) and \(B\) be two non-empty subsets of nodes separated by separator \(SP\subseteq V^{\prime\prime}_{1}\) and containing at least a node of \(M\) each. We let \(m_{A}\in A\bigcap M\) and \(m_{B}\in B\bigcap M\). Any walk from \(m_{A}\) to \(m_{B}\) must pass through \(SP\), but nodes in \(SP\) cannot be internal nodes in any walk. Trivially, walks are not possible between \(m_{A}\) and \(m_{B}\) satisfying the degree constraints. We let \(MC=(M,EC)\) be a complete graph on \(M\) such that each edge in \(EC\) corresponds to an arbitrary walk without nodes in \(V^{\prime\prime}_{1}\) as an internal node (the endpoints can be in \(V^{\prime\prime}_{1}\)). Following Lemma 2, this graph exists. In the following, we suppose that \(V^{\prime\prime}_{1}\) does not contain any separator cutting the set \(M\). Remember that \(V^{\prime\prime}_{1}\subseteq M\). Lemma 3: _If \(|V^{\prime\prime}_{1}|<3\), then hierarchies spanning \(M\) and satisfying the degree constraints exist._  
Proof: Based on the complete graph \(MC\), simple solutions can be constructed as follows. In \(MC\), Hamiltonian paths can be found. If \(|V^{\prime\prime}_{1}|=0\), we select an arbitrary Hamiltonian path. It corresponds to a Hamiltonian walk in \(G^{\prime\prime}\) trivially satisfying the constraints. If \(|V^{\prime\prime}_{1}|=2\), we select a Hamiltonian path \(P_{H}\) with the two nodes with degree-bound values of one as endpoints. Path \(P_{H}\) corresponds to walk \(W_{H}\) in \(G^{\prime\prime}\). Since the internal nodes in \(P_{H}\) are not in \(V^{\prime\prime}_{1}\), walk \(W_{H}\) does not contain internal nodes in \(V^{\prime\prime}_{1}\). The degree constraints are satisfied and the node set \(M\) is covered.