PreprintCC BY 4.0arXiv
Spanning subhypergraphs with degree constraints
Abstract
An old result of Tutte states that any d-regular graph contains a spanning subgraph in which every vertex has degree k or k+1, for every 1≤ k≤ d. We generalize this statement to hypergraphs, showing, for example, that every $3$-uniform d-regular hypergraph contains a subgraph in which all degrees are k, k+1 or k+2, for every 1≤ k≤ d. This statement is best possible in the sense that the corresponding statement with only two allowed consecutive values is not true. We provide generalizations of this statement to higher uniformities and discuss several open problems.
Related
- Spanning tree with bounded degree sum of two adjacent vertices
- Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
- Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
- Local Resilience for Containment of Bounded Degree Spanning Subgraphs
- Clique counts under degree and matching constraints
BibTeX
@misc{alon2026spanning,
title = {{Spanning subhypergraphs with degree constraints}},
author = {Noga Alon and Penny Haxell and Aleksa Milojević and Jacques Verstraëte},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13002},
eprint = {2609.13002},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13002},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spanning subhypergraphs with degree constraints
AU - Noga Alon
AU - Penny Haxell
AU - Aleksa Milojević
AU - Jacques Verstraëte
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.13002
UR - https://arxiv.org/abs/2609.13002
AB - An old result of Tutte states that any d-regular graph contains a spanning subgraph in which every vertex has degree k or k+1, for every 1≤ k≤ d. We generalize this statement to hypergraphs, showing, for example, that every $3$-uniform d-regular hypergraph contains a subgraph in which all degrees are k, k+1 or k+2, for every 1≤ k≤ d. This statement is best possible in the sense that the corresponding statement with only two allowed consecutive values is not true. We provide generalizations of this statement to higher uniformities and discuss several open problems.
ER -