# Degree-Constrained Minimum Spanning Hierarchies in Graphs
## 4 Necessary and Sufficient Conditions for the Existence of a Solution  
Degree-constrained spanning hierarchies do not always exist in the case of heterogeneous degree bounds. In this section, we formulate conditions for their existence. Figure 2: A DCMSH represented by its labeled tree \(T\) in the graph \(G\). Remember, we suppose a connected graph and \(V_{m}\subseteq V\) indicates the subset of nodes with degree bound \(m\). Trivially, the nodes in \(V_{1}\) must be leaves in any solution. Lemma 1: _If the specified leaf node set \(V_{1}\) is empty, hierarchies spanning \(V\) and satisfying the degree constraints exist._  
Proof: A simple solution can be constructed as follows. Let \(W\) be a walk following an MST in \(G\). In \(W\) each node occurrence has a degree of at most two. The degree constraints are satisfied and the node set is covered. Trivially, Lemma 1 gives a sufficient condition. The complementary case is when \(V_{1}\) is not empty. The necessary and sufficient conditions for this case are discussed next. Lemma 2: _If \(V_{1}\) contains a separator (removing a separator makes a connected graph disconnected), there is no hierarchy spanning \(V\) and satisfying the degree constraints._  
Proof: Let \(A\) and \(B\) be two non-empty subsets of nodes separated by a separator \(S\subseteq V_{1}\). Any path from a node in \(A\) to a node in \(B\) must pass through \(S\) but nodes in \(S\) can not be internal nodes in any path. Trivially, no paths exist between nodes in \(A\) and nodes in \(B\) satisfying the degree constraints in \(V_{1}\). A necessary condition can be formulated: \(V_{1}\) must be free of any separator. If \(V_{1}\) is not a separator but a subset of \(V_{1}\) is a separator, this later isolates some nodes in \(V_{1}\). Consequently, a spanning hierarchy satisfying the degree constraints does not exist. Figure 3 illustrates this case. Here, \(V_{1}=\{b,c,d\}\) is not a separator but the subset \(\{b,d\}\) is. Suppose there is no separator in \(V_{1}\). Lemmas 3 and 5 indicate that a set \(V_{1}\) without a separator is necessary but not sufficient for the existence of a spanning hierarchy satisfying the degree constraints. Further sufficient conditions are given by Lemmas 4, 6 and 7. Lemma 3: _If there is no node with a degree bound greater than 2 and there are more than two nodes with a degree bound \(1\) (\(|V_{1}|>2\)), there is no hierarchy spanning \(V\) and satisfying the constraints._  
Proof: Each node in \(V_{1}\) must be a leaf in the spanning hierarchy \((T,h,G)\) (and trivially in the corresponding tree \(T\)). Since \(|V_{1}|>2\), the tree \(T\) and the hierarchy must have more than two leaves. Because \(V_{d}=\emptyset,\forall d>2\), the degree of internal nodes in \(T\) is equal to 2. \(T\) is a path and as such it can not have more than two leaves. Lemma 4: _If \(|V_{1}|\leq 2\), hierarchies spanning \(V\) and satisfying the constraints exist._  
Proof: Suppose there are two nodes \(a\) and \(b\) with degree bound \(1\). A complete graph \(MC\) can be constructed in which the edges represent the shortest paths in \(G\) that contain neither \(a\) nor \(b\) as an internal node. These paths exist because \(V_{1}\) does not contain any separators. In \(MC\), Hamiltonian paths exist whose endpoints coincide with \(a\) and \(b\). Each Hamiltonian path corresponds to a Hamiltonian walk (a Hamiltonian walk covers the node set and can return several times to certain nodes) in the original graph covering the node set and respecting the degree constraints. These walks are solutions. The same demonstration is trivial with only one node in \(V_{1}\). In this case, one end of the Hamiltonian paths can be freely chosen in \(MC\). Figure 3: \(V_{1}\) is not a separator, but contains a separator. **Lemma 5**. : _Let us suppose that \(|V\setminus V_{1}|=1\) and let \(v_{b}\) the node in \(V\setminus V_{1}\). If the degree bound \(D(v_{b})<|V_{1}|\), there is no hierarchy spanning \(V\) and respecting the constraints._  
Proof.