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,\dots ,q_d)$ satisfies $$\sum _{i=0}^d{q}_i=n,\sum _{i=0}^{d}i{q}_i\equiv 0(\mathrm{mod}2),\left|q_i-\frac{n}{d+1}\right|\le 1(0\le i\le d),$$ then there is a spanning subgraph $H\subseteq G$ such that $$m(H,i)=q_i(0\le i\le d).$$

18 pages. Comments and suggestions are welcome