pith. sign in

arxiv: 2606.30612 · v1 · pith:6AI7JNPBnew · submitted 2026-06-29 · 🧮 math.CO

Nearly-uniform degree distributions in spanning subgraphs

Richard Montgomery , Alexey Pokrovskiy , Benny Sudakov This is my paper

Pith reviewed 2026-06-30 04:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords regular graphsspanning subgraphsdegree distributionirregular subgraphsgraph theory
0
0 comments X

The pith

Every d-regular n-vertex graph with d=o(n) has a spanning subgraph with nearly uniform degrees from 0 to d.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any d-regular graph on n vertices, provided d is much smaller than n, always contains a spanning subgraph in which the degrees are spread out evenly. For each possible degree value i from 0 to d, roughly the same number of vertices, specifically about n divided by d plus one, have exactly degree i in the subgraph. This result proves a conjecture of Alon and Wei about the existence of irregular subgraphs in regular graphs. A reader would care because it reveals that even highly regular graphs can be reduced to subgraphs with highly irregular, balanced degree distributions without any additional assumptions on the graph.

Core claim

When d=o(n), every d-regular n-vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each 0≤i≤d, there are (1+o(1))n/(d+1) vertices with degree i. This proves a conjecture of Alon and Wei on irregular subgraphs and strengthens a previous result of Fox, Luo and Pham.

What carries the argument

A spanning subgraph with a nearly uniform degree distribution across 0 to d.

If this is right

  • It proves the Alon-Wei conjecture on irregular subgraphs under the given conditions.
  • It strengthens the result of Fox, Luo and Pham by applying to all d-regular graphs.
  • Regular graphs admit subgraphs with balanced representation of all intermediate degrees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This shows that regular graphs have high flexibility in their spanning subgraphs' degree profiles.
  • Similar results may hold for graphs with maximum degree d when d=o(n).

Load-bearing premise

The host graph is an arbitrary d-regular graph on n vertices with no further restrictions such as being random or having good expansion properties.

What would settle it

A d-regular graph on n vertices with d=o(n) where in every spanning subgraph, the number of vertices of some degree i deviates from n/(d+1) by more than o(n).

read the original abstract

We show that, when $d=o(n)$, every $d$-regular $n$-vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each $0\leq i\leq d$, there are $(1+o(1))n/(d+1)$ vertices with degree $i$. This proves a conjecture of Alon and Wei on irregular subgraphs and strengthens a previous result of Fox, Luo and Pham.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript proves that when d = o(n), every d-regular n-vertex graph G contains a spanning subgraph H such that for each i in {0, ..., d}, the number of vertices with deg_H(v) = i is (1 + o(1)) n / (d + 1). The result is stated uniformly over all such host graphs, proves the Alon-Wei conjecture on irregular subgraphs, and strengthens the earlier theorem of Fox-Luo-Pham.

Significance. If the proof is correct, the result is a notable advance in extremal graph theory: it supplies an existence theorem for balanced degree sequences that requires no expansion, girth, or randomness hypotheses on the host graph and holds uniformly for the entire class of d-regular graphs under the single condition d = o(n). This removes a key technical barrier present in prior work and directly resolves a stated conjecture.

minor comments (1)
  1. The abstract states the main theorem but the provided text contains no section headings, proof outline, or equation references; a full manuscript with numbered sections and a clear proof structure is required for technical verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and for recognizing the result as a notable advance that resolves the Alon-Wei conjecture uniformly over all d-regular graphs with d=o(n). No specific major comments appear in the report, so we have nothing further to address point-by-point at this stage. We remain available to supply additional proof details or clarifications if the uncertainty concerns verification of the argument.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is a pure existence theorem in extremal graph theory: for every d-regular n-vertex graph with d=o(n), there exists a spanning subgraph whose degrees hit each value in {0,...,d} on asymptotically equal numbers of vertices. The statement is uniform over the entire class of d-regular graphs and contains no parameter fitting, no renormalization of fitted quantities as predictions, and no load-bearing self-citation that reduces the claimed result to a prior result by the same authors. The proof is presented as a direct strengthening of Fox-Luo-Pham together with a resolution of the Alon-Wei conjecture; both the statement and the logical structure are independent of the target conclusion by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is a pure existence theorem in graph theory; it relies on standard axioms of finite graphs and regularity but introduces no new free parameters, invented entities, or ad-hoc axioms visible from the abstract.

axioms (1)
  • standard math Basic axioms of undirected simple graphs and the definition of d-regularity.
    Invoked implicitly in the statement that the host graph is d-regular.

pith-pipeline@v0.9.1-grok · 5588 in / 1250 out tokens · 38105 ms · 2026-06-30T04:43:31.422856+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

19 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Addario-Berry, K

    L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, and A. Thomason. Vertex-colouring edge-weightings.Combinatorica, 27(1):1–12, 2007

    2007

  2. [2]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. John Wiley & Sons, 2016

    2016

  3. [3]

    Alon and F

    N. Alon and F. Wei. Irregular subgraphs.Combinatorics, Probability and Computing, 32(2):269– 283, 2023. 14

    2023

  4. [4]

    R. J. Faudree and J. Lehel. Bound on the irregularity strength of regular graphs. InColloq. Math. Soc. J´ anos Bolyai, volume 52, pages 247–256. Combinatorics Eger, 1987

    1987

  5. [5]

    R. J. Faudree, R. H. Schelp, M. S. Jacobson, and J. Lehel. Irregular networks, regular graphs and integer matrices with distinct row and column sums.Discrete Mathematics, 76(3):223–240, 1989

    1989

  6. [6]

    J. Fox, S. Luo, and H. T. Pham. On random irregular subgraphs.Random Structures & Algorithms, 64(4):899–917, 2024

    2024

  7. [7]

    Frieze, R

    A. Frieze, R. J. Gould, M. Karo´ nski, and F. Pfender. On graph irregularity strength.Journal of Graph Theory, 41(2):120–137, 2002

    2002

  8. [8]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random graphs. John Wiley & Sons, 2011

    2011

  9. [9]

    Kalkowski, M

    M. Kalkowski, M. Karo´ nski, and F. Pfender. Vertex-coloring edge-weightings: towards the 1–2–3- conjecture.Journal of Combinatorial Theory, Series B, 100(3):347–349, 2010

    2010

  10. [10]

    An Optimal Space Lower Bound for Approximating MAX-CUT

    M. Kapralov and D. Krachun. An optimal space lower bound for approximating max-cut.arXiv preprint arXiv:1811.10879, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  11. [11]

    Karo´ nski, T

    M. Karo´ nski, T. Luczak, and A. Thomason. Edge weights and vertex colours.Journal of Combi- natorial Theory, Series B, 91(1):151–157, 2004

    2004

  12. [12]

    R. Keusch. A solution to the 1–2–3 conjecture.Journal of Combinatorial Theory, Series B, 166:183–202, 2024

    2024

  13. [13]

    Lov´ asz

    L. Lov´ asz. Subgraphs with prescribed valencies.Journal of Combinatorial Theory, 8(4):391–416, 1970

    1970

  14. [14]

    Ma and S

    J. Ma and S. Xie. Finding irregular subgraphs via local adjustments.Journal of Combinatorial Theory, Series B, 174:71–98, 2025

    2025

  15. [15]

    Przyby lo and F

    J. Przyby lo and F. Wei. On the asymptotic confirmation of the Faudree–Lehel conjecture for general graphs.Combinatorica, 43(4):791–826, 2023

    2023

  16. [16]

    Przyby lo and F

    J. Przyby lo and F. Wei. Short proof of the asymptotic confirmation of the Faudree–Lehel conjec- ture.The Electronic Journal of Combinatorics, P4.27, 2023

    2023

  17. [17]

    Shirazi and J

    H. Shirazi and J. Verstra¨ ete. A note on polynomials andf-factors of graphs.The Electronic Journal of Combinatorics, N22, 2008

    2008

  18. [18]

    W. T. Tutte. The factors of graphs.Canadian Journal of Mathematics, 4:314–328, 1952

    1952

  19. [19]

    N. C. Wormald. The differential equation method for random graph processes and greedy algo- rithms. InLectures on approximation and randomized algorithms, pages 73–155, 1999. 15

    1999