Irregular Subgraphs

Noga Alon, Fan Wei

Published 2021-08-05Version 1

We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $d$-regular graph on $n$ vertices contains a spanning subgraph in which the number of vertices of each degree between $0$ and $d$ deviates from $\frac{n}{d+1}$ by at most $1$. The second is that every graph on $n$ vertices with minimum degree $\delta$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $\frac{n}{\delta+1}+1$. Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $n$. In particular we show that if $d^3 \log n \leq o(n)$ then every $d$-regular graph with $n$ vertices contains a spanning subgraph in which the number of vertices of each degree between $0$ and $d$ is $(1+o(1))\frac{n}{d+1}$. We also prove that any graph with $n$ vertices and minimum degree $\delta$ contains a spanning subgraph in which no degree is repeated more than $(1+o(1))\frac{n}{\delta+1}+2$ times.