On numbers of vertices of maximum degree in the spanning trees of a graph (Q1923502)

Let \(G\) be a connected graph and \({\mathcal T}(G)\) the set of all spanning trees of \(G\). For each \(T\in {\mathcal T}(G)\) let \(n_\Delta(T)\) be the number of vertices with maximum degree in \(T\). The authors show that \(N(G):=\{n_\Delta(T)\mid T\in {\mathcal T}(G)\}\) is a set of consecutive integers or the union of two such sets if \(G\) is a cactus (this means that each edge belongs to at most one cycle) or \(G\) has \(p\) vertices and \(p+1\) edges. An example at the end of the paper shows that \(N(G)\) may have an arbitrary number of ``gaps'' if \(G\) is a connected graph without any restriction.