{"id":"arxiv/2609.19777","url":"https://arxiv.org/abs/2609.19777","tags":["math.CO"],"score":0,"title":"Nearly Spanning Regular Subgraphs","domain":"math.CO","source":"arxiv","authors":["Varun Sivashankar"],"reviews":0,"subject":"math.CO","summary":"Alon and Mubayi asked whether, for every integer $k\\ge1$ and every $\\varepsilon>0$, there exists $r_0=r_0(k,\\varepsilon)$ such that every $r$-regular graph on $n$ vertices with $r\\ge r_0$ contains a $k$-regular subgraph covering at least $(1-\\varepsilon)n$ vertices. Previously, the conjecture was known for $k\\in\\{1,2\\}$ and for $k$ and $r$ both even. We answer this question affirmatively for general $k$ and $r$ with $\\varepsilon=O_k(r^{-1/2})$. For $k=2$ and every odd $r\\ge3$, we show that $\\varepsilon=1/(r^2-3)$ suffices which is best possible.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}