{"id":"arxiv/2604.25725","url":"https://arxiv.org/abs/2604.25725","tags":["math.PR","math.CO"],"score":0,"title":"What is The Probability That A Random Graph With A Given Degree Sequence is Connected?","domain":"math.PR","source":"arxiv","authors":["Louigi Addario-Berry","Bruce Reed","Dao Chen Yuan"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-28","reactions":{}}