Irregular subgraph in a regular graph

Abstract

A conjecture of Alon and Wei states that, for any $d$-regular graph $G$ with $n$ vertices, there exists a spanning subgraph $H$ such that for all $0\le i\le d$, we have $m(H, i)$, the number of vertices in $H$ with degree $i$, is between $\frac{n}{d+1}-2$ and $\frac{n}{d+1}+2$. We prove the conjecture for all fixed $d$ when $n$ is sufficiently large. More precisely, if $q=(q_0,\ldots,q_d)$ satisfies $$ \sum_{i=0}^d q_i=n,\qquad \sum_{i=0}^d i q_i\equiv 0\pmod 2,\qquad \left|q_i-\frac{n}{d+1}\right|\le 1 \quad (0\le i\le d), $$ then there is a spanning subgraph $H\subseteq G$ such that $$ m(H,i)=q_i \qquad (0\le i\le d). $$

Disclosure

“grant number SIMIS-ID-2024-WE. The third author is grateful for the resources and facilities provided by SIMIS, which were essential for the completion of this work. During the development and preparation of this work, the authors used ChatGPT for pre- liminary, non-authoritative assistance, including organizational discussion, language polishing, and exploratory discussion of possible proof strategies. The tool was not treated as a math- ematical authority or cited source. No m”

PDF page 18

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-24T00:34:12.480Z

Structural counts