Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size
Let G(p,q) be a connected graph. Following the notation of the author, a connected spanning subgraph of G having i edges and j pendant vertices (j\(\geq 1)\) is called an \(S_ 0(i,j)\)-subgraph, and a connected spanning subgraph with i mutually edge-disjoint cycles, j pendant vertices, and \(p+i-1\) edges is called an \(S_ 1(i,j)\)-subgraph. Two interpolation theorems are obtained. If G has \(S_ 0(i,k)\)-subgraphs for \(k=m\) and \(k=n\), where \(m<n\), then it has \(S_ 0(i,k)\)-subgraphs for each k, \(m<k<n\). If, in addition, G has at least \(2(p+i-1)\) edges, then the analogous result holds for \(S_ 1(i,j)\)-subgraphs. The corresponding interpolation theorem for spanning trees was proved constructively by \textit{S. Schuster} [J. Graph Theory 7, 203-208 (1983; Zbl 0482.05032)].
scientific article; zbMATH DE number 3920531