# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 4 Necessary and Sufficient Conditions for the Existence of a Solution
If \(|V^{\prime\prime}_{1}|=1\), one endpoint of the selected Hamiltonian path must be the node with degree bound one, and the other endpoint can be selected arbitrarily. As in the previous case, the corresponding walk is a solution. Now, let us suppose that  
The nodes in \(V_{1}^{\prime\prime}\) must be leaves in any spanning hierarchy, and there is no return from leaves. Consequently, only one occurrence of \(v_{b}\) exists in any hierarchy. This occurrence of \(v_{b}\) can have at most \(D(v_{b})\) neighbors, but \(|V_{1}^{\prime\prime}|>D(v_{b})\). Lemma 5: _If \(|V^{\prime\prime}\setminus V_{1}^{\prime\prime}|=1\), and \(D(v_{b})\geq|V_{1}^{\prime\prime}|\) of the node \(v_{b}\in V^{\prime\prime}\setminus V_{1}^{\prime\prime}\), a spanning hierarchy respecting the degree constrains exists._  
Proof: The graph \(G^{\prime\prime}\) is a star with the central node \(v_{b}\) such that \(D(v_{b})\geq|V_{1}|\). The nodes in \(V_{1}^{\prime\prime}\) are connected to it (there is no separator in \(V_{1}^{\prime\prime}\)). Since the leaves are in \(M\) and \(D(v_{b})\geq|V_{1}^{\prime\prime}|\), the star covers \(M\) and satisfies the degree constraints. The cases where \(|V^{\prime\prime}\setminus V_{1}^{\prime\prime}|>1\) with an arbitrary number of nodes in \(V_{1}^{\prime\prime}\) are covered by the following lemma. We prove that one node with a degree bound of at least two and another with a degree bound greater than two are sufficient to build degree-constrained hierarchies spanning the set \(M\) for an arbitrary number of nodes in \(V^{\prime\prime}\). As previously stated, we assume that there is no separator in \(V_{1}^{\prime\prime}\). Lemma 6: _If \(|V^{\prime\prime}\setminus V_{1}^{\prime\prime}|\geq 2\) (there are at least two nodes with degree bound greater than one) and \(|V^{\prime\prime}\setminus\{V_{2}^{\prime\prime}\cup V_{1}^{\prime\prime}\}|\geq 1\) (there is at least one node with degree bound greater than two), a Steiner hierarchy respecting the degree constraints exists._  
Proof: We let \(b\in V^{\prime\prime}\setminus V_{1}^{\prime\prime}\) be a node with \(D(b)\geq 2\), and another \(c\in V^{\prime\prime}\setminus V_{1}^{\prime\prime}\) with \(D(c)>2\). A degree-constrained hierarchy can be constructed as follows. Because there is no separator in \(V_{1}^{\prime\prime}\) separating the nodes of \(M\), each node in \(M\setminus(\{b\}\cup\{c\})\) can be connected to \(c\) with a path and each path respects the degree constraints. The set of paths can be partitioned into groups such that there are at most \(D(c)-2\) paths in every group. Since one endpoint of the paths is the node \(c\), each group corresponds to a spider respecting the degree constraints and having an occurrence of \(c\) as the central node. The different occurrences of \(c\) can be chained by a walk visiting the node \(b\) (having a degree bound of at least two) such that the degree of each central node occurrence is at most \(D(c)\). The obtained structure is a degree-constrained hierarchy spanning the node-set \(M\). A simple example shows the chain of the spiders in Figure 2.  
The necessary and sufficient conditions for the existence of a degree-constrained minimum Steiner hierarchy covering a given node set \(M\) in \(G\) can be formulated as follows. Remember that the graph obtained after the suppression of nodes in \(V_{1}\setminus M\) is \(G^{\prime}=(V^{\prime},E^{\prime})\) and the connected component in \(G^{\prime}\) that contains the node set \(M\) is \(G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})\). Theorem 4.1: _Let the set of conditions in \(G^{\prime\prime}\) be as follows: A: \(G^{\prime}\) contains a connected component with all nodes of \(M\); B: There is no separator composed from nodes of \(V_{1}^{\prime\prime}\) separating nodes in \(M\) into at least two sub-sets in \(G^{\prime\prime}\); C: \(|V_{1}^{\prime\prime}|<3\) (there are at most two nodes with degree bound \(1\) in \(G^{\prime\prime}\));  
Figure 2: Illustration of Lemma 6.