# Degree-Constrained Minimum Spanning Hierarchies in Graphs
## 4 Necessary and Sufficient Conditions for the Existence of a Solution
: Since there is no separator in \(V_{1}\), the nodes in \(V_{1}\) are connected to \(v_{b}\). (suppose that a node \(a\in V_{1}\) is not connected to \(v_{b}\) but to another node \(b\in V_{1}\). \(b\) separates \(a\) from the other nodes) The nodes in \(V_{1}\) must be leaves in any spanning hierarchy. Since there is no return from leaves, there is only one occurrence of \(v_{b}\) in any hierarchy. This occurrence of \(v_{b}\) can have at most \(D(v_{b})\) neighbors, but \(|V_{1}|>D(v_{b})\). **Lemma 6**. : _If \(|V\setminus V_{1}|=1\), and \(D(v_{b})\geq|V_{1}|\) of the node \(v_{b}\in V\setminus V_{1}\), a spanning hierarchy respecting the degree constraints exists._  
Proof. : The graph \(G\) contains a star with a central node \(D(v_{b})\geq|V_{1}|\) and the nodes in \(V_{1}\) are connected to it (there is no separator in \(V_{1}\)). Since \(D(v_{b})\geq|V_{1}|\), and the star satisfies the degree constraints. Lemmas 3 and 5 indicate cases where there are several nodes in \(V_{1}\) and there is no spanning hierarchy respecting the degree constraints. The following lemma formulates a sufficient condition. **Lemma 7**. : _If \(|V\setminus V_{1}|\geq 2\) (there are at least two nodes with a degree bound greater than \(1\)) and \(|V\setminus\{V_{2}\cup V_{1}\}|\geq 1\) (there is at least one node with a degree bound greater than \(2\)), a spanning hierarchy respecting the degree constraints exists._  
Proof. : Let \(b\) be a node with \(D(b)\geq 2\), and another \(c\) with \(D(c)>2\). A degree-constrained spanning hierarchy can be constructed as follows. Because there is no separator in \(V_{1}\), each node in \(V\setminus(\{b\}\cup\{c\})\) can be connected to \(c\) with a path satisfying the degree constraints. The set of paths can be partitioned 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 at least \(2\)) such that the degree of each central node is at most \(D(c)\). The obtained structure is a degree-constrained hierarchy spanning the node-set. Figure 4 illustrates a spanning hierarchy corresponding to Lemma 7. The occurrences of the node \(c\) are the central nodes of spiders which are connected by paths passing through the node \(b\). Notice that it is not the \"best\" spanning hierarchy. The reader can easily find hierarchies containing fewer edges while respecting the constraints. The following theorem formulates necessary and sufficient conditions for the existence of degree-constrained spanning hierarchies. **Theorem 1**. : _Let the set of conditions be as follows: A: \(V_{1}\) is empty B: there is no separator in \(V_{1}\) C: \(|V_{1}|\leq 2\) (there are at most two nodes with degree bound \(1\))_  
Figure 4: Illustration of Lemma 7. (**a**) indicates the graph and (**b**) its spanning hierarchy. \(D\): \(|V_{1}|>2\) and the nodes in \(V_{1}\) are neighbor nodes of a node \(v\) s.t. \(v\in V_{m},m\geq|V_{1}|\)  
\(E\): \(|V\setminus V_{1}|\geq 2\) (there are at least two nodes with degree bound greater than \(1\)) and  
\(|V\setminus(V_{2}\cup V_{1})|\geq 1\) (there is at least one node with a degree bound greater than \(2\)). A hierarchy spanning all the nodes of a connected graph and respecting non-uniform capacity degree constraints can be found, if \(A\vee(B\wedge(C\lor D\lor E))\)  
Proof. : Following Lemma 1, condition A is sufficient. If \(A\) is not true, the second part of the expression, i.e., \(X=B\wedge(C\lor D\lor E)\) gives a sufficient condition for the existence of a solution as it can be proven easily. In any case, \(V_{1}\) cannot contain a separator (condition \(B\) is necessary, as a consequence of Lemma 2), and one of the cases \(C,D\) or \(E\) must be true. Following Lemmas 4, 6 and 7 these conditions together with B are sufficient.