pith. machine review for the scientific record. sign in

arxiv: 2605.07923 · v1 · submitted 2026-05-08 · 🧮 math.CO · math.PR

Recognition: no theorem link

The number and structure of connected graphs with a fixed degree sequence

Remco van der Hofstad, Sasha Bell, Serte Donderwinkel

Pith reviewed 2026-05-11 03:17 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords connected graphsdegree sequenceconfiguration modelgiant componentasymptotic enumerationswitching argumentsparse graphsrandom graphs
0
0 comments X

The pith

The number of connected graphs with a fixed degree sequence is identified up to exponential order by realizing them as giant components in a larger configuration model.

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

The paper determines the asymptotic count of connected graphs on n vertices with a prescribed degree sequence, in the sparse case where edges grow linearly with n, up to multiplicative factors of exp(o(n)). It models each such connected graph as the giant component inside a larger configuration model whose degree distribution is tuned so that this giant component matches the target degrees with high probability. A switching procedure then adjusts the graph to have exactly the required degrees while leaving the leading exponential term unchanged. This count is useful because it gives the growth rate for these graphs and supports analysis of their local structure and the probabilities of rare events under the uniform distribution over them.

Core claim

We identify the number of connected graphs with a fixed degree sequence up to the exponential order by viewing a connected graph with a given degree distribution as the realization of the giant component in a larger configuration model, and carefully choosing the degree distribution of the larger graph so that it is likely that its giant component has the required degree distribution. To ensure that the connected graph has exactly the correct degrees, we use a switching argument. Additionally, we obtain results on rare event probabilities and describe the local structure of a uniform connected graph with a fixed degree sequence.

What carries the argument

Embedding the target connected graph as the giant component of a larger configuration model with a tuned degree distribution, followed by a switching argument to enforce exact degrees.

Load-bearing premise

A degree distribution exists for the larger configuration model such that its giant component has exactly the target degree distribution with high probability, and the switching step preserves the exponential order of the count.

What would settle it

For an explicit degree sequence and large n, compute or simulate the exact number of connected graphs and check whether it matches the exponential growth rate predicted by the embedding construction within the claimed error bounds.

read the original abstract

We study connected graphs with a fixed degree sequence, in the sparse setting where the number of edges grows linearly in the number of vertices. Using the relation to the configuration model, we identify the number of such connected graphs up to the exponential order. We do this by viewing a connected graph with a given degree distribution as the realization of the giant component in a larger configuration model, and carefully choosing the degree distribution of the larger graph so that it is likely that its giant component has the required degree distribution. To ensure that the connected graph has exactly the correct degrees, we use a switching argument. Additionally, we obtain results on rare event probabilities and describe the local structure of a uniform connected graph with a fixed degree sequence.

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

2 major / 2 minor

Summary. The manuscript develops an asymptotic enumeration (up to exponential order) for the number of connected simple graphs with a prescribed degree sequence in the sparse regime (average degree bounded). The central strategy embeds the target sequence as the degree sequence of the giant component in a configuration model on a larger vertex set, selects the super-distribution so that this match occurs with probability exp(o(n)), and applies a switching argument to enforce exact degrees while preserving the leading exponential term. Additional results describe rare-event probabilities for the configuration model and the local weak limit of a uniform random connected graph with the given sequence.

Significance. If the error-term controls hold, the work supplies the first exponential-order formula for connected graphs with fixed degrees in the constant-average-degree regime, extending classical configuration-model enumeration results. The local-structure description and rare-event analysis are natural by-products that could be useful for sampling and statistical inference on networks. The approach re-uses standard giant-component and branching-process machinery but requires a non-trivial tilting argument whose quantitative details determine whether the exponential order is correctly identified.

major comments (2)
  1. [Abstract and Introduction] The abstract and the strategy paragraph in the introduction assert that a degree distribution on the larger vertex set can be chosen so the giant component realizes the target sequence with probability exp(o(n)). No explicit construction of this super-distribution, no statement of the required large-deviation or local-CLT bounds, and no uniformity argument over the tilting parameter appear in the provided text. Because the offspring-law perturbation is potentially Ω(1), the probability could be exp(-Θ(n)) rather than exp(o(n)), which would change the leading exponential term for the count; this is load-bearing for the main claim.
  2. [Switching argument (location not numbered in excerpt)] The switching step is invoked to correct residual degree discrepancies after extracting the giant component. The manuscript does not supply the exponential-order bound on the number of switches or the probability that the switched graph remains simple and connected; without these estimates it is unclear whether the switching multiplies the count by a factor exp(o(n)) or by a larger term.
minor comments (2)
  1. [Notation section] Notation for the target degree sequence versus the super-distribution should be introduced with explicit symbols (e.g., d vs. d*) and kept consistent across statements of the main theorem.
  2. [Local structure theorem] The local weak limit result would benefit from a short statement of the limiting branching-process offspring distribution in terms of the original degree sequence.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable comments on our manuscript. We address each major comment below and outline the revisions we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract and Introduction] The abstract and the strategy paragraph in the introduction assert that a degree distribution on the larger vertex set can be chosen so the giant component realizes the target sequence with probability exp(o(n)). No explicit construction of this super-distribution, no statement of the required large-deviation or local-CLT bounds, and no uniformity argument over the tilting parameter appear in the provided text. Because the offspring-law perturbation is potentially Ω(1), the probability could be exp(-Θ(n)) rather than exp(o(n)), which would change the leading exponential term for the count; this is load-bearing for the main claim.

    Authors: We agree that more explicit details are necessary to substantiate this key step. In the revised version, we will include an explicit construction of the super-distribution by solving the system of equations derived from the branching process approximation to match the target degree sequence exactly in expectation. We will also provide the large-deviation bounds and local CLT estimates, along with a uniformity argument showing that the tilting parameter can be chosen in a way that the probability is indeed exp(o(n)) rather than exp(-Θ(n)). This will be added to both the abstract and the introduction, with full proofs in the main body. revision: yes

  2. Referee: [Switching argument (location not numbered in excerpt)] The switching step is invoked to correct residual degree discrepancies after extracting the giant component. The manuscript does not supply the exponential-order bound on the number of switches or the probability that the switched graph remains simple and connected; without these estimates it is unclear whether the switching multiplies the count by a factor exp(o(n)) or by a larger term.

    Authors: This is a valid point regarding the quantitative control of the switching procedure. We will revise the manuscript to include explicit bounds: the expected number of switches is bounded by a constant, and the probability that a switched configuration remains simple and connected is 1 - o(1). These estimates ensure that the switching contributes only a exp(o(n)) factor to the count. The details will be provided in the dedicated section on the switching argument, drawing on standard techniques for configuration models. revision: yes

Circularity Check

0 steps flagged

No load-bearing circularity; standard configuration-model embedding plus switching argument

full rationale

The derivation embeds the target connected graph as the giant component of a larger configuration model whose degree distribution is chosen so the giant component matches the target sequence with high probability, then applies switching to enforce exact degrees. This is a standard technique relying on independently established results about configuration models and giant components (e.g., branching-process approximations and local limit theorems), not a self-definition or fitted-input prediction. No equation reduces the count to a parameter fitted from the same data, no uniqueness theorem is imported from the authors' prior work, and the switching factor is shown separately to be exp(o(n)). The central exponential-order claim therefore retains independent content from external random-graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the standard configuration model, known giant-component properties in the sparse regime, and the existence of a suitable degree distribution for the auxiliary graph; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math The configuration model produces a random multigraph with a prescribed degree sequence whose connectivity properties are governed by known branching-process approximations in the sparse regime.
    Invoked when the paper states that the connected graph is realized as the giant component of a larger configuration model.
  • domain assumption A switching operation can be applied to adjust degrees while preserving the exponential growth rate of the number of graphs.
    Used to ensure the final graph has exactly the target degrees.

pith-pipeline@v0.9.0 · 5418 in / 1413 out tokens · 29347 ms · 2026-05-11T03:17:16.543989+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

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

  1. [1]

    Addario-Berry and G

    L. Addario-Berry and G. Crudele. Universal diameter bounds for random graphs with given degrees. arXiv:2507.10759 [math.PR], 2025. 1

    work page arXiv 2025

  2. [2]

    What is The Probability That A Random Graph With A Given Degree Sequence is Connected?

    L. Addario-Berry, B. Reed, and D. C. Yuan. What is the probability that a random graph with a given degree sequence is connected? arXiv:2604.25725 [math.PR], 2026. 1

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  3. [3]

    D. Aldous. Theζ(2) limit in the random assignment problem.Random Structures Algorithms,18(4):381–418, 2001. ISSN 1042-9832. doi: 10.1002/rsa.1015. 22

    work page doi:10.1002/rsa.1015 2001

  4. [4]

    Aldous and R

    D. Aldous and R. Lyons. Processes on unimodular random networks.Electron. J. Probab.,12(54):1454–1508, 2007. ISSN 1083-6489. doi: 10.1214/EJP.v12-463. 3

    work page doi:10.1214/ejp.v12-463 2007

  5. [5]

    Aldous and J.M

    D. Aldous and J.M. Steele. The objective method: probabilistic combinatorial op- timization and local weak convergence. InProbability on discrete structures, vol- ume110ofEncyclopaedia Math. Sci., pages 1–72. Springer, 2004. doi: 10.1007/ 978-3-662-09444-0 1. 22

    work page 2004

  6. [6]

    Arman, P

    A. Arman, P. Gao, and N. Wormald. Fast uniform generation of random graphs with given degree sequences.Random Structures Algorithms,59(3):291–314, 2021. ISSN 1042-9832,1098-2418. doi: 10.1002/rsa.21004. 1

    work page doi:10.1002/rsa.21004 2021

  7. [7]

    A. D. Barbour and A. R¨ ollin. Central limit theorems in the configuration model.Ann. Appl. Probab.,29(2):1046–1069, 2019. ISSN 1050-5164. doi: 10.1214/18-AAP1425. 9

    work page doi:10.1214/18-aap1425 2019

  8. [8]

    S. Bell, S. Donderwinkel, and R. van der Hofstad. The structure of connected graphs with a fixed number of vertices and edges. In preparation., 2026+. 9

    work page 2026

  9. [9]

    E. A. Bender and E. R. Canfield. The asymptotic number of labelled graphs with given degree sequences.J. Combin. Theory (A),24:296–307, 1978. 1

    work page 1978

  10. [10]

    E. A. Bender, E. R. Canfield, and B. D. McKay. The asymptotic number of labeled connected graphs with a given number of vertices and edges.Random Structures Algorithms,1(2):127–169, 1990. ISSN 1042-9832. doi: 10.1002/rsa.3240010202. 1, 9

    work page doi:10.1002/rsa.3240010202 1990

  11. [11]

    Benjamini and O

    I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs.Electron. J. Probab.,6(23):13 pp. (electronic), 2001. ISSN 1083-6489. doi: 10.1214/EJP.v6-96. 22

    work page doi:10.1214/ejp.v6-96 2001

  12. [12]

    Bhamidi, A

    S. Bhamidi, A. Budhiraja, P. Dupuis, and R. Wu. Rare event asymptotics for explo- ration processes for random graphs.The Annals of Applied Probability, 32, 04 2022. doi: 10.1214/21-AAP1704. 2

    work page doi:10.1214/21-aap1704 2022

  13. [13]

    Bollob´ as

    B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.European J. Combin.,1(4):311–316, 1980. ISSN 0195-6698. 1, 4

    work page 1980

  14. [14]

    Bollob´ as

    B. Bollob´ as. The evolution of sparse graphs. InGraph theory and combinatorics (Cambridge, 1983), pages 35–57. Academic Press, London, 1984. 1, 9

    work page 1983

  15. [15]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan. An old approach to the giant component problem.J. Combin. Theory Ser. B,113:236–260, 2015. ISSN 0095-8956. 8, 10, 22

    work page 2015

  16. [16]

    Bordenave

    C. Bordenave. Lecture notes on random graphs and probabilistic combinatorial op- timization. Version April 8, 2016. URLwww.math.univ-toulouse.fr/ ~bordenave/ coursRG.pdf, 2016. 22

    work page 2016

  17. [17]

    Bordenave and P

    C. Bordenave and P. Caputo. Large deviations of empirical neighborhood distribution in sparse random graphs.Probab. Theory Rel. Fields,163(1-2):149–222, 2015. ISSN 0178-8051. doi: 10.1007/s00440-014-0590-8. 8

    work page doi:10.1007/s00440-014-0590-8 2015

  18. [18]

    Federico and R

    L. Federico and R. van der Hofstad. Critical window for connectivity in the config- uration model.Combin. Probab. Comput.,26(5):660–680, 2017. ISSN 0963-5483. 1, 2

    work page 2017

  19. [19]

    Gao and N

    P. Gao and N. Wormald. Enumeration of graphs with a heavy-tailed degree sequence. Adv. Math.,287:412–450, 2016. ISSN 0001-8708. doi: 10.1016/j.aim.2015.09.002. 1

    work page doi:10.1016/j.aim.2015.09.002 2016

  20. [20]

    Gao and N

    P. Gao and N. Wormald. Uniform generation of random regular graphs.SIAM J. Com- put.,46(4):1395–1427, 2017. ISSN 0097-5397,1095-7111. doi: 10.1137/15M1052779. 28 SASHA BELL, SERTE DONDER WINKEL, AND REMCO V AN DER HOFSTAD 1

    work page doi:10.1137/15m1052779 2017

  21. [21]

    Gao and N

    P. Gao and N. Wormald. Uniform generation of random graphs with power-law degree sequences. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1741–1758. SIAM, Philadelphia, PA, 2018. ISBN 978-1- 61197-503-1. doi: 10.1137/1.9781611975031.114. 1

    work page doi:10.1137/1.9781611975031.114 2018

  22. [22]

    van der Hofstad.Random Graphs and Complex Networks

    R. van der Hofstad.Random Graphs and Complex Networks. Volume 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016. URLhttps://www.win.tue.nl/ ~rhofstad/NotesRGCN.pdf. 2, 4, 10, 11, 13

    work page 2016

  23. [23]

    van der Hofstad.Random Graphs and Complex Networks

    R. van der Hofstad.Random Graphs and Complex Networks. Volume 2. Cambridge University Press, 2024. URLhttps://www.win.tue.nl/ ~rhofstad/NotesRGCNII. pdf. 5, 7, 8, 11, 13, 22, 23

    work page 2024

  24. [24]

    van der Hofstad

    R. van der Hofstad. The giant in random graphs is almost local. arXiv:2103.11733 [math.PR], 2021. 22

    work page arXiv 2021

  25. [25]

    van der Hofstad and J

    R. van der Hofstad and J. Spencer. Counting connected graphs asymptotically.Eu- ropean J. Combin.,27(8):1294–1320, 2006. ISSN 0195-6698. 9

    work page 2006

  26. [26]

    S. Janson. Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas.Probab. Surv.,4:80–145 (electronic), 2007. ISSN 1549-5787. 1

    work page 2007

  27. [27]

    S. Janson. The probability that a random multigraph is simple.Combinatorics, Probability and Computing,18(1-2):205–225, 2009. 1

    work page 2009

  28. [28]

    S. Janson. The probability that a random multigraph is simple. II.J. Appl. Probab., 51A(Celebrating 50 Years of The Applied Probability Trust):123–137, 2014. ISSN 0021-9002. doi: 10.1239/jap/1417528471. 1

    work page doi:10.1239/jap/1417528471 2014

  29. [29]

    Janson and M

    S. Janson and M. Luczak. A new approach to the giant component problem.Random Structures Algorithms,34(2):197–216, 2009. ISSN 1042-9832. doi: 10.1002/rsa.20231. 11

    work page doi:10.1002/rsa.20231 2009

  30. [30]

    Kamˇ cev, A

    N. Kamˇ cev, A. Liebenau, and N. Wormald. Asymptotic enumeration of hypergraphs by degree sequence.Adv. Comb., pages Paper No. 1, 36, 2022. ISSN 2517-5599. doi: 10.19086/aic.32357. 1

    work page doi:10.19086/aic.32357 2022

  31. [31]

    Liebenau and N

    A. Liebenau and N. Wormald. Asymptotic enumeration of digraphs and bipartite graphs by degree sequence.Random Structures Algorithms,62(2):259–286, 2023. ISSN 1042-9832,1098-2418. doi: 10.1002/rsa.21105. 1

    work page doi:10.1002/rsa.21105 2023

  32. [32]

    Liebenau and N

    A. Liebenau and N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph.J. Eur. Math. Soc. (JEMS),26(1):1–40,

    work page

  33. [33]

    doi: 10.4171/jems/1355

    ISSN 1435-9855,1435-9863. doi: 10.4171/jems/1355. 1

    work page doi:10.4171/jems/1355

  34. [34]

    T. Luczak. On the number of sparse connected graphs.Random Structures Algo- rithms,1(2):171–173, 1990. ISSN 1042-9832. 1, 9

    work page 1990

  35. [35]

    T. Luczak. Sparse random graphs with a given degree sequence. InRandom graphs, Vol. 2(Pozna´ n, 1989), pages 165–182. Wiley, 1992. 1

    work page 1989

  36. [36]

    McKay and N

    B. McKay and N. Wormald. Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2).Combinatorica,11(4):369–382, 1991

    work page 1991

  37. [37]

    B. D. McKay. Subgraphs of random graphs with specified degrees.Congressus Nu- merantium,33:213–223, 1981

    work page 1981

  38. [38]

    B. D. McKay. Subgraphs of random graphs with specified degrees. InProceedings of the International Congress of Mathematicians 2010. Hindustan Book Agency, 2011. doi: 10.1142/9789814324359 0155

    work page doi:10.1142/9789814324359 2010

  39. [39]

    B. D. McKay and N. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree.European J. Combin.,11(6):565–580, 1990. 1

    work page 1990

  40. [40]

    Pittel and N

    B. Pittel and N. Wormald. Counting connected graphs inside-out.J. Combin. Theory Ser. B,93(2):127–172, 2005. ISSN 0095-8956. doi: 10.1016/j.jctb.2004.09.005. 1, 9

    work page doi:10.1016/j.jctb.2004.09.005 2005

  41. [41]

    A. R´ enyi. On connected graphs. I.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.,4: 385–388, 1959. CONNECTED GRAPHS WITH GIVEN DEGREES 29

    work page 1959

  42. [42]

    J. Spencer. Enumerating graphs and Brownian motion.Comm. Pure Appl. Math., 50(3):291–294, 1997. ISSN 0010-3640. 1, 9

    work page 1997

  43. [43]

    N. Wormald. The asymptotic connectivity of labelled regular graphs.J. Combin. Theory Ser. B,31(2):156–167, 1981. ISSN 0095-8956. 1

    work page 1981

  44. [44]

    N. Wormald. Models of random regular graphs. InSurveys in combinatorics, 1999 (Canterbury), volume267ofLondon Math. Soc. Lecture Note Series, pages 239–298. Cambridge University Press, 1999. 1

    work page 1999

  45. [45]

    N. Wormald. Asymptotic enumeration of graphs with given degree sequence. In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, pages 3245–3264. World Sci. Publ., Hackensack, NJ, 2018. ISBN 978-981-3272-93-4; 978-981-3272-87-3. 1

    work page 2018

  46. [46]

    E. M. Wright. The number of connected sparsely edged graphs.J. Graph Theory,1 (4):317–330, 1977. ISSN 0364-9024. 1, 9

    work page 1977

  47. [47]

    E. M. Wright. The number of connected sparsely edged graphs. III. Asymptotic results.J. Graph Theory,4(4):393–407, 1980. ISSN 0364-9024. 1, 9 McGill University Email address:sasha.bell@mail.mcgill.ca University of Groningen Email address:s.a.donderwinkel@rug.nl Eindhoven University of Technology Email address:r.w.v.d.hofstad@tue.nl

    work page 1980