Almost Regular Subgraph of Sparse Graph

70 Views Asked by At

Definitions: A spanning subgraph of a graph $G$ is a subgraph of $G$ including all its vertices. An almost $r$-regular graph is a graph whose degrees are either $r$ or $r-1$.

Question: Suppose we have an arbitrarily large bipartite graph $G$ whose vertices' degrees are tightly concentrated in the range $[d_\min, d_\max]$ ($d_\max/d_\min \approx 1$, but $d_\max - d_\min$ may be quite large, definitely much larger than $1$). Is there some always some threshold $d_0 = d_0(r)$ so that when $d_\min > d_0$, there is always an almost $r$-regular spanning subgraph of $G$?

It's clear that there is not always an $r$-regular spanning subgraph of $G$. But is there always an almost $r$-regular spanning subgraph?