On spanning trees whose degrees are congruent to one modulo $\ell$

Abstract

An $\ell$-congruent spanning tree of a nontrivial connected graph is a spanning tree in which every vertex has degree congruent to one modulo $\ell$. This notion provides a common generalization of classical spanning trees and odd spanning trees. We show, via a constructive greedy algorithm, that every $n$-vertex graph $G$ satisfying $n\equiv2\pmod{\ell}$ and $δ(G)>\frac{(\ell-1)n}{\ell}$ has an $\ell$-congruent spanning tree. For the special case of odd spanning trees ($\ell=2$), our algorithmic approach simplifies the original proof by Zheng and Wu. We also derive formulas for the numbers of $\ell$-congruent spanning trees in complete graphs and complete bipartite graphs. These formulas specialize to the classical spanning-tree formulas when $\ell=1$ and to the corresponding odd-spanning-tree formulas when $\ell=2$.

Disclosure

“his paper. Acknowledgments This work is partially supported by the National Natural Science Foundation of China (Grant No. 12001006) and Wuhu Science and Technology Project, China (Grant No. 2024kj015). The authors acknowledge the use of Gemini 3.1 Pro for language polishing and detailed proofreading of the manuscript. References [1] C. Berge, Graphs and Hypergraphs, North-Holland Math. Library, Vol. 6, North- Holland Publishing Co., Amsterdam-London; American Elsevier Publishing”

PDF page 11

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T05:11:15.112209Z

Structural counts