The Probability That a Random Multigraph is Simple

Abstract

Consider a random multigraph G * with given vertex degrees d 1 ,. . ., d n , constructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the number of edges $\tfrac12\sumd\to\infty$ , the probability that the multigraph is simple stays away from 0 if and only if $\sumdd=O\bigpar{\sumd}$ . This was previously known only under extra assumptions on the maximum degree max i d i . We also give an asymptotic formula for this probability, extending previous results by several authors.