pith. sign in

arxiv: 2607.06465 · v1 · pith:ETKYJLAL · submitted 2026-07-07 · math.CO

Irregular subgraph in a regular graph

pith:ETKYJLALopen to challenge →

classification math.CO
keywords fracqquadsubgraphconjecturegraphregularspanningthere
0
0 comments X
read the original 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). $$

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.