{"id":"arxiv/2608.11990","url":"https://arxiv.org/abs/2608.11990","tags":["math.CO"],"score":0,"title":"On spanning trees whose degrees are congruent to one modulo $\\ell$","domain":"math.CO","source":"arxiv","authors":["Zhidan Yan","Wei Wang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}