pith. machine review for the scientific record. sign in

arxiv: 2604.25725 · v1 · submitted 2026-04-28 · 🧮 math.PR · math.CO

Recognition: unknown

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

Bruce Reed, Dao Chen Yuan, Louigi Addario-Berry

Authors on Pith no claims yet

Pith reviewed 2026-05-07 15:26 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random graphsdegree sequencesconnectivitydisconnected graphsuniform modelgraphical sequencesprobability bounds
0
0 comments X

The pith

A random graph with a prescribed degree sequence is connected with high probability provided there are sufficiently few vertices of degree 1 or 2.

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

The paper bounds the probability that a uniform random graph with a given feasible degree sequence is disconnected, in terms of how many vertices have small degrees. Specifically, when the number of degree-1 vertices is little-o of the square root of the number of edges and degree-2 vertices is little-o of the number of edges, this probability tends to zero. When there are no vertices of degree 1 or 2 at all, the disconnection probability is at most a constant times n to the fourth over m to the sixth. A sympathetic reader would care because this clarifies when the uniform random graphs with fixed degrees produce connected networks, which is key for studying random networks without isolated parts.

Core claim

Let G(D) be a graph chosen uniformly at random among all graphs with a given feasible degree sequence D having no isolated vertices and m edges. The authors upper-bound the probability that G(D) is disconnected in terms of the numbers of vertices of low degree. Their main results are that this probability is o(1) whenever there are o(√m) degree-1 vertices and o(m) degree-2 vertices, and that it is O(n⁴/m⁶) when there are no degree-1 or degree-2 vertices.

What carries the argument

Upper bounds on the disconnection probability of the uniform random graph G(D) derived from counting arguments that depend on the counts of degree-1 and degree-2 vertices.

If this is right

  • The graph is asymptotically almost surely connected whenever there are o(√m) degree-1 vertices and o(m) degree-2 vertices.
  • An explicit polynomial upper bound O(n^4/m^6) holds on the disconnection probability when the minimum degree is at least 3.
  • The combinatorial tools developed apply directly to obtain similar disconnection bounds for other small values of d.
  • Connectivity holds with high probability in the uniform model under the same low-degree conditions that are already known to be sufficient in the configuration model.

Where Pith is reading between the lines

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

  • The bounds suggest that in large networks with prescribed degrees, the total number of degree-1 and degree-2 vertices controls the chance of small isolated components forming.
  • Because the uniform model and configuration model are close in total variation for many degree sequences, the same conditions likely guarantee connectivity in the configuration model as well.
  • Numerical checks on small n with all degrees at least 3 could verify whether the O(n^4/m^6) bound is sharp or can be improved.

Load-bearing premise

The degree sequence must be graphical with no zero-degree vertices so that the uniform distribution over realizing graphs is well-defined.

What would settle it

Generate many realizations of a specific graphical degree sequence with no degree-1 or degree-2 vertices and large m, then measure the empirical fraction that are disconnected and check whether it stays below C n^4/m^6 for moderate constants C.

Figures

Figures reproduced from arXiv: 2604.25725 by Bruce Reed, Dao Chen Yuan, Louigi Addario-Berry.

Figure 1
Figure 1. Figure 1: Example of a switching at {xy, uv} to get edges {xv, uy} from graphs H to J. In this and all subsequent figures of switchings, edges used in the switching are red and edges used to undo the switching are blue. Dashed lines represent the absence of edges, unless otherwise noted in the caption. A B view at source ↗
Figure 2
Figure 2. Figure 2: If every graph in A has at most ∆(A) switchings (in red) into B, while every graph in B has at least δ(B) switchings (in blue) into A, then |B| ≤ ∆(A) δ(B) |A|. Given two disjoint families A and B of graphs with degree sequence D, we can compare their relative sizes by considering switchings between them. Specifically if for every graph H in A there are at most ∆(A) graphs in B which can be obtained from H… view at source ↗
Figure 3
Figure 3. Figure 3: The starting vertex and the first 3 iterations of an exploration. The figures illustrate the start of each iteration. The Hi are depicted in red for i = 0, . . . , 3 and the open half-edges are black. we build a subgraph H of G[V (T)] and the submatching N of RD corresponding to H. In each iteration, for some vertex v ′ in the current tree we expose all the matching edges leaving half-edges incident to v ′… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of Xi ≥ Li(Li − 1). The fact that vi had the least amount of open half-edges forces each other vertex hit by a back edge to have at least Li − 1 other open half-edges. To conclude this section, we explain the reason for our choice of vi as the vertex of T with open half-edges minimizing the number of such edges. This choice of vi allows us to deterministically bound Li which helps bound the… view at source ↗
Figure 5
Figure 5. Figure 5: Switching used in the proof of Lemma 3.2: we switch away degree 1 neighbours of u (vertex a) one-by-one for non-neighbours of u of degree 2 or more (vertex v). x a v y u S view at source ↗
Figure 6
Figure 6. Figure 6: The switching used in the proof of Lemma 3.3. The vertex a is added into S after the switch. The dashed black lines indicate that no paths of length at most 4 exist between u and v outside of S, which implies the absence of the edges xv and ay. Lemma 3.3. Let D be such that m is large enough and n1 ≤ n(1 − log m). Fix u, v ∈ [n] with d(u), d(v) ≥ (log m) 4 and such that d(u)d(v) ≥ m(log m) 4 . Then the pro… view at source ↗
Figure 7
Figure 7. Figure 7: First switching in the proof of Lemma 3.5. The black lines indicate no paths of length at most 3 exist between n, u, implying the absence of the blue edges. For any G in Fi for i ≤ 10 log m there are at least d(u) 2(log m) 2 − 2i > d(u) 3(log m) 2 choices of xa and at least d(v) − 2i > d(v) 2 choices of yv. On the other hand, for a G′ in Fi+1, there are at most 2(i + 1)m choices of {xv, ya}. Thus for 0 ≤ i… view at source ↗
Figure 8
Figure 8. Figure 8: Second switching in the proof of Lemma 3.5. Every switching makes a member of W into a neighbour of u. The dotted black line indicates there are no paths between u, v outside of Z, which implies the absence of the blue edges. in G − n and at most 2(i + 1)2m1/8 vertices of H at distance within 3 of n. We show P  ∪i≤m1/8Fi view at source ↗
Figure 9
Figure 9. Figure 9: Switching used in the proof of Lemma 3.6. The black dotted lines indicate that there are no edge between Z and Sv outside of Y , and no paths between Su and Sv outside of Z. The edge yv′ ∈/ Y , so y /∈ Z. The vertices u ′ and x are not in Z, so the fact that there are no paths between Su and Sv outside of Z ensures the absence of u ′v ′ and xy. edges consisting of (i) an edge from one of the at least m1/9 … view at source ↗
Figure 10
Figure 10. Figure 10: Switching used in the proof of Lemma 3.8. Here, the three types of “bad” edges are all illustrated: an edge not in E(H) from v back into V (H), or onto a degree 1 or 2 vertex. Vertex b has degree at least 3. Furthermore, X j≤i:dj (vj )< √m (log m)2 (3dj (vj ))2 ≤ 3 √ m (log m) 2 X j≤i dj (vj ) ≤ 3m3/2 (log m) 2 so by Azuma’s inequality [1], P  Yi < − m log m  < exp  −m2 (log m) −2 3m3/2(log m)−2  < e−… view at source ↗
read the original abstract

An $n$-tuple $D=(d(1),\dots,d(n))$ is a \emph{feasible degree sequence} if there is a graph on $\{1,\dots,n\}$ such that $i$ has degree $d(i)$. Any such graph will have $m=\sum_{i=1}^n d(i)/2$ edges. Letting $G(D)$ be a graph chosen uniformly from those with the given degree sequence, we upper-bound the probability that $G(D)$ is disconnected based on the number of vertices of degree $d$ for small $d$, and develop a powerful tool for proving such bounds. If there are any vertices of degree zero the probability $G$ is disconnected is $1$, so we assume there are no such vertices. Our results then imply that if there are $o(\sqrt{m})$ vertices of degree $1$ and $o(m)$ vertices of degree 2 then with high probability $G$ is connected, while if there are no vertices of degree 1 or 2 then the probability $G$ is disconnected is $O(\frac{n^4}{m^6})$.

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 / 2 minor

Summary. The manuscript develops a combinatorial-probabilistic tool to upper-bound the disconnection probability of the uniform random graph G(D) on a feasible degree sequence D with no zero-degree vertices and m edges. It concludes that o(√m) degree-1 vertices together with o(m) degree-2 vertices imply that G(D) is connected with high probability, while the absence of both degree-1 and degree-2 vertices yields a disconnection probability of O(n⁴/m⁶). The bounds are obtained directly from the developed tool without parameter fitting.

Significance. If the stated bounds hold, the work supplies concrete, quantitative criteria for connectivity in the uniform model over prescribed degree sequences, extending classical results on random graphs with given degrees. The general tool for deriving disconnection bounds is a strength that may apply to other properties; the argument is direct, handles feasibility and minimum-degree conditions explicitly, and avoids circularity. This is a useful advance for network modeling and random-graph theory.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'develop a powerful tool' would be strengthened by a one-sentence indication of the tool's main mechanism (e.g., counting or coupling argument) so readers can assess its scope immediately.
  2. [Introduction] The definition m = (1/2)∑ d(i) is used throughout; a single early display equation collecting all standing notation would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. We are pleased that the significance of the combinatorial-probabilistic tool and its direct bounds on disconnection probability were recognized.

read point-by-point responses

  1. Referee: No major comments were provided; the report consists of a summary, significance statement, and acceptance recommendation.

    Authors: We appreciate the referee's recognition that the bounds hold directly from the developed tool without parameter fitting, that the argument handles feasibility and minimum-degree conditions explicitly, and that the tool may apply to other properties. This aligns with our goals of extending classical results on random graphs with given degrees. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained combinatorial argument

full rationale

The paper develops an upper bound on the disconnection probability for the uniform model G(D) on feasible degree sequences with no isolated vertices, using direct combinatorial-probabilistic tools. The stated implications (whp connectivity when o(√m) degree-1 vertices and o(m) degree-2 vertices; O(n⁴/m⁶) bound with no degree-1 or -2 vertices) follow from this bound under the explicitly stated feasibility and minimum-degree conditions. No load-bearing steps reduce by construction to fitted parameters, self-definitions, or self-citation chains; the argument is independent of the target results and does not rename known patterns or smuggle ansatzes via prior work by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on the standard definition of a graphical degree sequence and the uniform model over all realizations; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption D is a feasible (graphical) degree sequence
    Required for the set of graphs with degree sequence D to be non-empty.
  • domain assumption No vertices of degree zero
    Explicitly stated; otherwise disconnection probability is trivially 1.

pith-pipeline@v0.9.0 · 5505 in / 1222 out tokens · 61293 ms · 2026-05-07T15:26:21.983787+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    math.CO 2026-05 unverdicted novelty 7.0

    The number of connected graphs with a given sparse degree sequence is identified up to exponential order by viewing them as giant components in a suitably chosen configuration model and applying a switching argument.

Reference graph

Works this paper leans on

13 extracted references · cited by 1 Pith paper

  1. [1]

    Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, 19(3):357 – 367, 1967

    Kazuoki Azuma. Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, 19(3):357 – 367, 1967. 14

    1967

  2. [2]

    Bekessy, P

    A. Bekessy, P. Bekessy, and Janos Komlos. Asymptotic enumeration of regular matrices. Studia Scientiarum Mathematicarum Hungarica, 7, 01 1972. 3

    1972

  3. [3]

    Random regular graphs of non-constant degree: Connectivity and hamiltonicity.Combinatorics, Probability and Computing, 11(3):249–261,

    Colin Cooper, Alan Frieze, and Bruce Reed. Random regular graphs of non-constant degree: Connectivity and hamiltonicity.Combinatorics, Probability and Computing, 11(3):249–261,

  4. [4]

    Critical window for connectivity in the config- uration model.Combinatorics, Probability and Computing, 26(5):660–680, 2017

    Lorenzo Federico and Remco Van der Hofstad. Critical window for connectivity in the config- uration model.Combinatorics, Probability and Computing, 26(5):660–680, 2017. 5

    2017

  5. [5]

    Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity.Random Structures & Algorithms, 62(4):911–934, 2023

    Pu Gao and Yuval Ohapkin. Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity.Random Structures & Algorithms, 62(4):911–934, 2023. 5, 27

    2023

  6. [6]

    A remark on the existence of finite graphs.Casopis Pest

    V´ aclav Havel. A remark on the existence of finite graphs.Casopis Pest. Mat., 80:477–480,

  7. [7]

    How to determine if a random graph with a fixed degree sequence has a giant component.Probability Theory and Related Fields, 170(1):263–310, 2018

    Felix Joos, Guillem Perarnau, Dieter Rautenbach, and Bruce Reed. How to determine if a random graph with a fixed degree sequence has a giant component.Probability Theory and Related Fields, 170(1):263–310, 2018. 5

    2018

  8. [8]

    Sparse random graphs with a given degree sequence

    Tomasz Luczak. Sparse random graphs with a given degree sequence. InRandom Graphs, volume 2, pages 165–182, 1992. 5

    1992

  9. [9]

    Subgraphs of random graphs with specified degrees

    Brendan D McKay. Subgraphs of random graphs with specified degrees. InCongressus Nu- merantium Volume 33, pages 213–223, 1981. 3

    1981

  10. [10]

    A critical point for random graphs with a given degree sequence.Random Structures & Algorithms, 6(2-3):161–180, 1995

    Michael Molloy and Bruce Reed. A critical point for random graphs with a given degree sequence.Random Structures & Algorithms, 6(2-3):161–180, 1995. 5

    1995

  11. [11]

    James K. Senior. Partitions and their representative graphs.American Journal of Mathemat- ics, 73(3):663–689, 1951. 3

    1951

  12. [12]

    The asymptotic connectivity of labelled regular graphs.Journal of Combinatorial Theory, Series B, 31(2):156–167, 1981

    Nicholas C Wormald. The asymptotic connectivity of labelled regular graphs.Journal of Combinatorial Theory, Series B, 31(2):156–167, 1981. 2, 3, 5

    1981

  13. [13]

    Nicholas C. Wormald. The asymptotic distribution of short cycles in random regular graphs. Journal of Combinatorial Theory, Series B, 31(2):168–182, 1981. 1

    1981