# Subgraph probability of random graphs with specified degrees and
applications to chromatic number and connectivity

Pu Gao
University of Waterloo
<EMAIL_ADDRESS>Research supported by NSERC. Yuval Ohapkin
University of Waterloo
<EMAIL_ADDRESS>
###### Abstract

Given a graphical degree sequence ${\bf d}=(d_{1},\ldots,d_{n})$, let
${\mathcal{G}}(n,{\bf d})$ denote a uniformly random graph on vertex set $[n]$
where vertex $i$ has degree $d_{i}$ for every $1\leq i\leq n$. We give upper
and lower bounds on the joint probability of an arbitrary set of edges in
${\mathcal{G}}(n,{\bf d})$. These upper and lower bounds are approximately
what one would get in the configuration model, and thus the analysis in the
configuration model can be translated directly to ${\mathcal{G}}(n,{\bf d})$,
without conditioning on that the configuration model produces a simple graph.
Many existing results of ${\mathcal{G}}(n,{\bf d})$ in the literature can be
significantly improved with simpler proofs, by applying this new probabilistic
tool. One example we give is about the chromatic number of
${\mathcal{G}}(n,{\bf d})$.

In another application, we use these joint probabilities to study the
connectivity of ${\mathcal{G}}(n,{\bf d})$. When $\Delta^{2}=o(M)$ where
$\Delta$ is the maximum component of ${\bf d}$, we fully characterise the
connectivity phase transition of ${\mathcal{G}}(n,{\bf d})$. We also give
sufficient conditions for ${\mathcal{G}}(n,{\bf d})$ being connected when
$\Delta$ is unrestricted.

##  1 Introduction

Given a graphical degree sequence ${\bf d}=(d_{1},\ldots,d_{n})$, let
${\mathcal{G}}(n,{\bf d})$ denote a uniformly random graph on vertex set $[n]$
where vertex $i$ has degree $d_{i}$ for every $1\leq i\leq n$. We also use the
same notation ${\mathcal{G}}(n,{\bf d})$ for the support of
${\mathcal{G}}(n,{\bf d})$, i.e. the set of graphs with degree sequence ${\bf
d}$. Unless otherwise specified, there is usually no confusion from the
context whether ${\mathcal{G}}(n,{\bf d})$ refers to a set or a random graph
from this set, and we will specify it if there is confusion. We say ${\bf d}$
is graphical if the set ${\mathcal{G}}(n,{\bf d})$ is nonempty. In the special
case where $d_{i}=d$ for every $1\leq i\leq n$, ${\mathcal{G}}(n,{\bf d})$ is
a uniformly random $d$-regular graph. Random graphs with specified degree
sequences are among the most studied random graph models. However, unlike the
binomial random graph ${\mathcal{G}}(n,p)$, edge probabilities in
${\mathcal{G}}(n,{\bf d})$ are correlated. In fact, even estimating the
probability of a single edge in ${\mathcal{G}}(n,{\bf d})$ can be challenging.
That makes analysing ${\mathcal{G}}(n,{\bf d})$ difficult. A common tool used
for analysing ${\mathcal{G}}(n,{\bf d})$ is the configuration model introduced
by Bollobás [3]. In the configuration model, each vertex is represented as a
bin containing $d_{i}$ points. Take a uniformly random perfect matching over
the total $M=\sum_{i=1}^{n}d_{i}$ points, and let $G^{*}$ be the multigraph
obtained by taking each pair in the matching as an edge. That is, if points
$p$ and $q$ are matched as a pair by the matching then $uv$ is an edge in
$G^{*}$ where $u$ contains $p$ and $v$ contains $q$. $G^{*}$ is a multigraph
because there can be more than one edge between two vertices. A simple
counting argument shows that every simple graph with degree sequence ${\bf d}$
corresponds to the same number of configurations, and thus, $G^{*}$,
conditioned to the set of simple graphs, has the same distribution as
${\mathcal{G}}(n,{\bf d})$. Suppose ${\bf d}$ is such that the probability
that $G^{*}$ is simple is bounded away from 0 for all large $n$, then any
property that holds a.a.s. in the configuration model must hold a.a.s. in
${\mathcal{G}}(n,{\bf d})$. Estimating edge probabilities in the configuration
model is quite easy, and hence, many properties of ${\mathcal{G}}(n,{\bf d})$
are obtained by analysing the configuration model. However, the probability
that $G^{*}$ is simple is bounded away from 0 only for ${\bf d}$ such that
$M=\Theta(n)$ and $M_{2}:=\sum_{i=1}^{n}d_{i}^{2}=O(n)$. This condition
significantly restricts the type of results one can get by translating from
the configuration model.

The purpose of this work is to develop probabilistic tools for translating
configuration model analysis to ${\mathcal{G}}(n,{\bf d})$ analysis for a rich
family of degree sequences. We will illustrate with examples and show how easy
it is to improve existing results and prove new properties of
${\mathcal{G}}(n,{\bf d})$ using the new tools we develop. Let $H$ be a graph
on $[n]$. Under some mild conditions on $H$ and ${\bf d}$, one of our main
results shows the following.

The probability that $H$ is a subgraph of ${\mathcal{G}}(n,{\bf d})$ is
approximately the probability that all edges in $H$ appear in the
configuration model.

Before formally stating the main results, we define a few necessary terms.
Given ${\bf d}=(d_{1},\ldots,d_{n})$, without loss of generality we may assume
that $d_{1}\geq d_{2}\geq\cdots\geq d_{n}$. Define

$\Delta=d_{1},\quad\delta=d_{n},\quad M=\sum_{i=1}^{n}d_{i},\quad J({\bf
d})=\sum_{i=1}^{\Delta}d_{i}.$

For any $S\subseteq[n]$ define

$d(S)=\sum_{i\in S}d_{i},\quad\Delta_{S}=\max_{i\in S}d_{i}.$

Given a graph $H$ on vertex set $[n]$, let $e(H)$ be the number of edges in
$H$, $\Delta(H)$ be the maximum degree of $H$, and let ${\bf
d}^{H}=(d^{H}_{1},\ldots,d^{H}_{n})$ denote the degree sequence of $H$. For
graphs on the same vertex set, e.g. on $[n]$, we may treat them as sets of
edges. Thus, if two graphs $H_{1}$ and $H_{2}$ are both on vertex set $[n]$,
we say $H_{1}$ and $H_{2}$ are disjoint if their edge sets are disjoint. Given
a graph $H$ on $[n]$, let $H^{+}$ denote the event that
$H\subseteq{\mathcal{G}}(n,{\bf d})$, i.e. $H$ is a subgraph of
${\mathcal{G}}(n,{\bf d})$, and let $H^{-}$ denote the event that
$H\cap{\mathcal{G}}(n,{\bf d})=\emptyset$. Given two degree sequences ${\bf
d}$ and ${\bf d}^{\prime}$ defined on the same set of vertices, we say ${\bf
d}\preceq{\bf d}^{\prime}$ if $d_{i}\leq d^{\prime}_{i}$ for every $i$.

Typically we consider a sequence of degree sequences indexed by $n$, and we
are interested in properties of ${\mathcal{G}}(n,{\bf d})$ asymptotically when
$n\to\infty$. We say a property holds asymptotically almost surely (a.a.s.) if
the probability that the property holds goes to 1 as $n\to\infty$. We will use
standard Landau notation for asymptotic calculations. Given two sequences of
real numbers $a_{n}$ and $b_{n}$, we say $a_{n}=O(b_{n})$ if there exists a
constant $C>0$ such that $|a_{n}|\leq C|b_{n}|$ for every $n$. We say
$a_{n}=o(b_{n})$ if $b_{n}>0$ eventually (meaning for all sufficiently large
$n$) and $\lim_{n\to\infty}a_{n}/b_{n}=0$. We write $a_{n}=\Omega(b_{n})$ if
$a_{n}>0$ eventually and $b_{n}=O(a_{n})$. We say $a_{n}=\omega(b_{n})$ if
$a_{n}>0$ eventually and $b_{n}=o(a_{n})$.

###  1.1 Main results

####  1.1.1 Subgraph probabilities

Our first result concerns the conditional edge probabilities in
${\mathcal{G}}(n,{\bf d})$.

######  Theorem 1.

Let $H_{1}$ and $H_{2}$ be two disjoint graphs on $[n]$. Suppose that ${\bf
d}^{H_{1}}\preceq{\bf d}$, and $uv\notin H_{1}\cup H_{2}$. Then,

$\displaystyle{\mathbb{P}}(uv\in{\mathcal{G}}(n,{\bf d})\mid
H_{1}^{+},H_{2}^{-})$ $\displaystyle\leq$
$\displaystyle\frac{(d_{u}-d^{H_{1}}_{u})(d_{v}-d^{H_{1}}_{v})}{M-2e(H_{1})}\cdot
f({\bf d},H_{1},H_{2})$ $\displaystyle{\mathbb{P}}(uv\in{\mathcal{G}}(n,{\bf
d})\mid H_{1}^{+},H_{2}^{-})$ $\displaystyle\geq$
$\displaystyle\frac{(d_{u}-d^{H_{1}}_{u})(d_{v}-d^{H_{1}}_{v})}{M-2e(H_{1})}\cdot
g({\bf d},H_{1},H_{2})$

where

$\displaystyle f({\bf d},H_{1},H_{2})$ $\displaystyle=$
$\displaystyle\left(1-\frac{3J({\bf
d})+\Delta(8+d_{u}^{H_{2}}+d_{v}^{H_{2}})}{M-2e(H_{1})}-\frac{2e(H_{2})\Delta^{2}}{(M-2e(H_{1}))^{2}}+\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\right)^{-1}$
$\displaystyle g({\bf d},H_{1},H_{2})$ $\displaystyle=$
$\displaystyle\left(1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta}{M-2e(H_{1})}\right)\left(1+\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\right)^{-1}.$

By setting proper conditions on ${\bf d}$ we obtain an asymptotic value of
${\mathbb{P}}(uv\in{\mathcal{G}}(n,{\bf d})\mid H_{1}^{+},H_{2}^{-})$ as
follows, which is a direct corollary of Theorem 1.

######  Corollary 2.

Let $H_{1}$ and $H_{2}$ be two disjoint graphs on $[n]$. Suppose that ${\bf
d}^{H_{1}}\preceq{\bf d}$, and $uv\notin H_{1}\cup H_{2}$. Suppose further
that

$J({\bf d})+\Delta\cdot\Delta(H_{2})=o(M-2e(H_{1})),\quad
e(H_{2})\Delta^{2}=o\big{(}(M-2e(H_{1}))^{2}\big{)}.$

Then,

${\mathbb{P}}(uv\in{\mathcal{G}}(n,{\bf d})\mid
H_{1}^{+},H_{2}^{-})=(1+o(1))\frac{(d_{u}-d^{H_{1}}_{u})(d_{v}-d^{H_{1}}_{v})}{M-2e(H_{1})+(d_{u}-d^{H_{1}}_{u})(d_{v}-d^{H_{1}}_{v})}.$

######  Remark 3.

If ${\bf d}$ is a degree sequence composed of i.i.d. copies of a power-law
variable with exponent between 2 and 3, then a.a.s. $J({\bf d})=o(M)$. In [13,
Lemma 3], Van der Hofstad, Southwell, Stegehuis and the first author proved
the asymptotic conditional probabilities as in Corollary 2 for such power-law
degree sequences when $e(H_{1})=O(1)$ and $e(H_{2})=0$. A few other papers
studied such conditional probabilities for regular or near-regular degree
sequences. Kim, Sudakov and Vu [17, Lemma 2.1] obtained the asymptotic value
of the conditional probability when $e(H_{1})=O(1)$, $e(H_{2})=0$ and
$d_{i}\sim d$ for all $i$ where $d=o(n)$ and $d=\omega(1)$. Díaz, Joos, Kühn
and Osthus [7, Lemmas 2.1 and 2.2] obtained the asymptotic value of such
conditional probabilities in a random $d$-regular $r$-uniform hypergraph. Our
corollary above generalises and strengthens all these results above (compared
with [7, Lemmas 2.1 and 2.2] for $r=2$, our corollary has more relaxed
conditions on $H_{1}$ and $H_{2}$ in addition to relaxed conditions on ${\bf
d}$). Our result is mostly comparable with McKay’s enumeration results [20],
which yield similar probabilities as in Corollary 2 but require stronger
conditions on $\Delta$. These are all for sparse degree sequences. For dense
${\bf d}$, such conditional probabilities are estimated in [1, 14, 22, 12].

Repeatedly applying Theorem 1 we obtain the following joint probability bounds
for an arbitrary set of edges, under some mild conditions. Given a graph $H$,
let $\partial(H)=\\{v:v\cap x\neq\emptyset\ \mbox{for some $x\in E(H)$}\\}$ be
the set of vertices that are incident to some edge in $H$.

######  Theorem 4.

Assume $H_{1}$ and $H_{2}$ are two disjoint graphs on $[n]$.

  1. (a)

If

$\mathfrak{R}({\bf d},H_{1},H_{2}):=\frac{6J({\bf
d})+2\Delta(8+2\Delta(H_{2}))}{M-2e(H_{1})}+\frac{4e(H_{2})\Delta^{2}}{(M-2e(H_{1}))^{2}}\leq
1,$

then

$\displaystyle{\mathbb{P}}\Big{(}H_{1}^{+}\mid
H_{2}^{-}\Big{)}\leq\prod_{i=1}^{n}(d_{i})_{d_{i}^{H_{1}}}\cdot\prod_{j=1}^{h}\frac{1+{\mathfrak{R}}({\bf
d},H_{1},H_{2})}{(M-2j+2)}.$

  2. (b)

If

$\mathfrak{r}({\bf d},H_{1},H_{2}):=\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta+\Delta_{\partial(H_{1})}^{2}}{M-2e(H_{1})}\leq
1,$

then

${\mathbb{P}}\Big{(}H_{1}^{+}\mid
H_{2}^{-}\Big{)}\geq\prod_{i=1}^{n}(d_{i})_{d_{i}^{H_{1}}}\cdot\prod_{j=1}^{h}\frac{1-{\mathfrak{r}}({\bf
d},H_{1},H_{2})}{(M-2j+2)}.$

By setting $H_{2}=\emptyset$ and proper conditions on ${\bf d}$ so that
$\mathfrak{R}({\bf d},H_{1},\emptyset)=o(1)$, we obtain the following useful
upper and lower bounds on the joint probability.

######  Corollary 5.

Let $H$ be a graph on $[n]$ and assume that ${\bf d}$ is a degree sequence
satisfying $J({\bf d})=o(M-2e(H))$. Then

${\mathbb{P}}(H^{+})\leq\prod_{i=1}^{n}(d_{i})_{d_{i}^{H}}\prod_{i=1}^{e(H)}\frac{1+o(1)}{M-2i+2}.$
(1)

If further we have $\Delta^{2}_{\partial(H)}=o((M-2e(H)))$ then the above
holds with equality.

######  Remark 6.

Similar bounds on ${\mathbb{P}}(H^{+})$ are given by McKay in [22, Theorem
2.1] with much more restrictive ${\bf d}$ and $H$.

######  Remark 7.

Although probability estimates similar to (1) appeared in the literature for
several times, such probabilities were not connected before to the
corresponding probabilities in the configuration model, and thus were never
used to automatically translate the analysis from the configuration model to
${\mathcal{G}}(n,{\bf d})$. This is one of our main contributions of this
work. We compare (1) with the probability in the configuration model. Let
$\sigma^{*}$ denote a uniformly random perfect matching over the $M$ points
produced by the configuration model, and let $G^{*}$ be the multigraph
corresponding to $\sigma^{*}$. Given a graph $H$ on $[n]$ with ${\bf
d}^{H}\preceq{\bf d}$, let ${\mathcal{P}}(H)$ be the set of matchings $\sigma$
of size $e(H)$ over the set of $M$ points whose corresponding graph is $H$.
Then $|{\mathcal{P}}(H)|=\prod_{i=1}^{n}(d_{i})_{d_{i}^{H}}$ and
${\mathbb{P}}(\sigma\subseteq\sigma^{*})=\prod_{i=1}^{e(H)}\frac{1}{M-2i+1}$.
Hence,

${\mathbb{P}}(H\subseteq
G^{*})\leq\sum_{\sigma\in{\mathcal{P}}(H)}{\mathbb{P}}\big{(}\sigma\subseteq\sigma^{*}\big{)}=\prod_{i=1}^{n}(d_{i})_{d_{i}^{H}}\prod_{i=1}^{e(H)}\frac{1}{M-2i+1}.$
(2)

Thus, under the condition $J({\bf d})=o(M-2e(H))$, our upper bound in (1)
differs from the corresponding probability bound (2) in the configuration
model by a relative $1+o(1)$ factor in each term of the product. Such an
approximation is enough to translate a lot of configuration model analysis to
${\mathcal{G}}(n,{\bf d})$. See examples in Sections 1.1.2.

Another advantage of using the configuration model is that, it is very easy to
bound the probability of having a certain number of edges joining two sets of
vertices. Given two subsets of vertices $S_{1},S_{2}\subseteq[n]$, let
$e(S_{1},S_{2})$ be the number of edges with one end in $S_{1}$ and the other
end in $S_{2}$. When $S_{1}=S_{2}$, $e(S_{1},S_{2})$ is simply the number of
edges induced by $S_{1}$. In the configuration model, the probability that
$e(S_{1},S_{2})\geq\ell$ is at most

$\binom{d(S_{1})}{\ell}\frac{(d(S_{2}))_{\ell}}{\prod_{i=1}^{\ell}(M-2i+1)}.$
(3)

In the following corollary we show a similar bound for this probability in
${\mathcal{G}}(n,{\bf d})$.

######  Corollary 8.

Suppose $S_{1},S_{2}\subseteq[n]$. Let $1\leq\ell<M/2$ be an integer. Assume
that ${\bf d}$ satisfies $J({\bf d})=o(M-2\ell)$. Then,

${\mathbb{P}}(e(S_{1},S_{2})\geq\ell)\leq\binom{d(S_{1})}{\ell}(d(S_{2}))_{\ell}\left(\prod_{i=1}^{\ell}\frac{1+o(1)}{M-2i+2}\right)\leq\binom{d(S_{1})}{\ell}\frac{(d(S_{2}))_{\ell}}{(M/2)_{\ell}(2+o(1))^{\ell}}.$
(4)

Remark. Since $J({\bf d})\leq\Delta^{2}$, both Corollaries 5 and 8 hold when
$J({\bf d})$ is replaced by $\Delta^{2}$.

Proof.  Let $\mathcal{H}_{\ell}$ denote the set of graphs on $[n]$ having
exactly $\ell$ edges, all of which have exactly one end in $S_{1}$ and the
other end in $S_{2}$. Let $\\{i_{1},\cdots,i_{k}\\}$ denote the set of
vertices in $S_{1}\cup S_{2}$. By the union bound and Corollary 5,

${\mathbb{P}}(e(S_{1},S_{2})\geq\ell)\leq\sum_{H\in{\mathcal{H}}_{\ell}}{\mathbb{P}}(H\subseteq{\mathcal{G}}(n,{\bf
d}))\leq\left(\prod_{i=1}^{\ell}\frac{1+o(1)}{M-2i+2}\right)\sum_{H\in{\mathcal{H}}_{\ell}}\prod_{j=1}^{k}(d_{i_{j}})_{d_{i_{j}}^{H}}.$

Next we give a combinatorial interpretation of
$\sum_{H\in\mathcal{H}_{\ell}}\prod_{j=1}^{k}(d_{i_{j}})_{d_{i_{j}}^{H}}$
above. Represent each vertex $i_{j}$ in $S_{1}\cup S_{2}$ by a bin containing
$d_{i_{j}}$ points. Given $H\in{\mathcal{H}}_{\ell}$, how many matchings of
size $\ell$ over $2\ell$ out of the total $d(S_{1}\cup S_{2})$ points are
there so that if $uv$ is an edge in $H$ then there is a point $p$ in bin $u$
and a point $q$ in bin $v$ such that $p$ and $q$ are matched by the matching?
It is easy to see that there are exactly
$\prod_{j=1}^{k}(d_{i_{j}})_{d_{i_{j}}^{H}}$ such matchings. Hence,
$\sum_{H\in\mathcal{H}_{\ell}}\prod_{j=1}^{k}(d_{i_{j}})_{d_{i_{j}}^{H}}$ is
bounded above by the total number of size-$\ell$ matchings where every pair
$(p,q)$ in the matching is of the form that $p$ is in some bin in $S_{1}$ and
$q$ is in some bin in $S_{2}$. There are $\binom{d(S_{1})}{\ell}$ ways to
choose the $\ell$ ends that are in bins in $S_{1}$ and there are
$(d(S_{2}))_{\ell}$ ways to choose the other ends from bins in $S_{2}$ and
match them to the $\ell$ ends chosen before. Hence,

$\sum_{H\in\mathcal{H}_{\ell}}\prod_{j=1}^{k}(d_{i_{j}})_{d_{i_{j}}^{H}}\leq\binom{d(S_{1})}{\ell}(d(S_{2}))_{\ell},$

and thus,

${\mathbb{P}}(e(S_{1},S_{2})\geq\ell)\leq\left(\prod_{i=1}^{\ell}\frac{1+o(1)}{M-2i+2}\right)\binom{d(S_{1})}{\ell}(d(S_{2}))_{\ell}=\binom{d(S_{1})}{\ell}\frac{(d(S_{2}))_{\ell}}{(M/2)_{\ell}(2+o(1))^{\ell}},$

as $\prod_{i=1}^{\ell}(M-2i+2)=(M/2)_{\ell}2^{\ell}$.

####  1.1.2 Chromatic number of ${\mathcal{G}}(n,{\bf d})$

Let $\chi(G)$ denote the chromatic number of graph $G$, i.e. the minimum
number of colours required to colour vertices of $G$ so that all pairs of
adjacent vertices receive distinct colours. It is known that a.a.s. the
chromatic number of a random $d$-regular graph is asymptotically $d/2\ln d$,
for $d=\omega(1)$ and $d=o(n)$; see [11, 5, 18]. In the paper [10] Frieze,
Krivelevich and Smyth asked under what conditions on ${\bf d}$ would we have
a.a.s. $\chi({\mathcal{G}}(n,{\bf d}))=\Theta(d/\ln d)$, where $d=M/n$ is the
average degree of graphs in ${\mathcal{G}}(n,{\bf d})$. Let
$D_{k}=\sum_{i=1}^{k}d_{i}$ and $M_{2}=\sum_{i=1}^{n}d_{i}^{2}$. It was shown
in [10] that if

  * (A1)

there exist constants $1/2<\alpha<1$, $\epsilon,K_{0}>0$ such that $D_{k}\leq
K_{0}dn(k/n)^{\alpha}$ for all $1\leq k\leq\epsilon n$;

  * (A2)

$\Delta^{5}=o(M_{2})$,

then a.a.s. $\chi({\mathcal{G}}(n,{\bf d}))=O(d/\ln d)$. On the other hand, if

  * (A3)

$\Delta^{4}=o(M_{1})$,

then a.a.s. $\chi({\mathcal{G}}(n,{\bf d}))=\Omega(d/\ln d)$.

We significantly relax the conditions (A2) and (A3) and obtain the following
result for $\chi({\mathcal{G}}(n,{\bf d}))$.

######  Theorem 9.

If ${\bf d}$ satisfies condition (A1) and $\Delta=o(n)$ then a.a.s.
$\chi({\mathcal{G}}(n,{\bf d}))=O(d/\ln d)$. If $J({\bf d})=o(M)$ then a.a.s.
$\chi({\mathcal{G}}(n,{\bf d}))=\Omega(d/\ln d)$.

The proof of Theorem 9 will be given in Section 2, which is obtained by
translating the existing analysis [10] from the configuration model to
${\mathcal{G}}(n,{\bf d})$. We believe that many other results of
${\mathcal{G}}(n,{\bf d})$ can be obtained or improved in a similar manner.
For instance, the order of the largest component of ${\mathcal{G}}(n,{\bf d})$
was determined by Molloy and Reed [23] for the so-called “well-behaved” degree
sequences. Their proof relies on an analysis in the configuration model. We
believe that most of the analysis can be immediately translated to
${\mathcal{G}}(n,{\bf d})$ by using the conditional edge probabilities in
Theorem 1. We also believe that the new probabilistic tools developed in
Section 1.1.1 will be useful in studying other properties of
${\mathcal{G}}(n,{\bf d})$. We give another example in Section 1.1.3.

####  1.1.3 Connectivity transition of ${\mathcal{G}}(n,{\bf d})$

The connectivity is one of the best studied graph properties for random
graphs. Erdős and Rényi [6] determined the threshold of the connectedness for
${\mathcal{G}}(n,p)$. Indeed, for every fixed integer $k\geq 1$, Erdős and
Rényi [6] determined when ${\mathcal{G}}(n,p)$ becomes $k$-connected. Random
graph ${\mathcal{G}}(n,p)$ becomes connected when isolated vertices disappear,
which happens when $p\approx\log n/n$. For $p$ in this range, the average
degree of the random graphs is around $\log n$ and there are very few vertices
of degree one or two, and these vertices are pair-wise far away in graph
distance. Consequently the vertices of degree one or two do not affect the
connectedness of ${\mathcal{G}}(n,p)$. The most natural sparser random graph
model for the study of connectivity would be ${\mathcal{G}}(n,{\bf d})$, and
it is natural to ask when are such random graphs connected. As we will see,
the vertices of degree one or two play crucial roles for the connectedness of
${\mathcal{G}}(n,{\bf d})$.

The first work about the connectivity of ${\mathcal{G}}(n,{\bf d})$ was by
Wormald [24] in 1981. In this pioneering work, the author studied the
connectivity of ${\mathcal{G}}(n,{\bf d})$ where $\delta\geq 3$ and $\Delta$
is bounded by some absolute constant $R$ (i.e. $R$ does not depend on $n$),
and proved that a.a.s. the connectivity of ${\mathcal{G}}(n,{\bf d})$ is equal
to $\delta$ for such degree sequences. Frieze [9] studied the connectivity of
random $d$-regular graphs where $3\leq d=o(n^{0.2})$, and proved that a.a.s. a
random $d$-regular graph is $d$-connected, for $d$ in the aforementioned
range. Later, Cooper, Frieze and Reed [4] extended this result to $3\leq d\leq
cn$ where $c>0$ is a sufficiently small constant. Łuczak [19] extended their
work to non-regular degree sequences, and considered also degree sequences
permitting $\delta=2$. Łuczak showed that, for any ${\bf d}$ where $\delta\geq
3$ and $\Delta\leq n^{0.01}$ then a.a.s. ${\mathcal{G}}(n,{\bf d})$ is
$\delta$-connected. When $\delta=2$ and $\Delta\leq n^{0.01}$ he characterised
the structure of ${\mathcal{G}}(n,{\bf d})$ and determined when is
${\mathcal{G}}(n,{\bf d})$ a.a.s. 2-connected. In a more recent work, Federico
and Van der Hofstad [8] considered degree sequences permitting $\delta=1$ and
fully charactersized the connectivity transition of ${\mathcal{G}}(n,{\bf d})$
for ${\bf d}\in{{\mathcal{D}}}$, where ${{\mathcal{D}}}=\\{{\bf
d}:M=\Theta(n),\sum_{i=1}^{n}d_{i}^{2}=O(n)\\}$. Let $n_{1}$ be the number of
components in ${\bf d}$ with value 1, and $n_{2}$ the number of components in
${\bf d}$ with value 2. Federico and Van der Hofstad showed that for ${\bf
d}\in{{\mathcal{D}}}$ that satisfies some additional “smoothness” condition,
${\mathcal{G}}(n,{\bf d})$ is a.a.s. connected if $n_{1}=o(\sqrt{n})$ and
$n_{2}=o(n)$, and ${\mathcal{G}}(n,{\bf d})$ is disconnected if
$n_{1}=\omega(\sqrt{n})$. All the work that we have discussed so far are for
${\bf d}$ where either the maximum degree is not large (at most $n^{0.01}$),
or ${\bf d}$ corresponds to a regular degree sequence, and the degree is
nearly sublinear (at most $cn$ for some sufficiently small $c$). For $d$
linear in $n$, Krivelevich, Sudakv, Vu and Wormald [18] proved several
properties of random $d$-regular graphs, including the connectivity. Recently,
Isaev, McKay and the first author [12] proved several properties including the
connectivity of ${\mathcal{G}}(n,{\bf d})$ for near-regular ${\bf d}$ where
$d=\omega(\log n)$ and $d_{i}\sim d$ for every $i$.

In this work, we characterise the connectivity transition of
${\mathcal{G}}(n,{\bf d})$ for a much larger family of degree sequences. For
the family of ${\bf d}$ where $J({\bf d})=o(M)$ (in particular, when
$\Delta^{2}=o(M)$) we fully characterise the phase transition of the
connectedness of ${\mathcal{G}}(n,{\bf d})$. When $\Delta$ is unrestricted we
give sufficient conditions under which ${\mathcal{G}}(n,{\bf d})$ is a.a.s.
connected.

We only consider degree sequences where $\delta\geq 1$ since otherwise
${\mathcal{G}}(n,{\bf d})$ is disconnected trivially. Given the degree
sequence ${\bf d}$ where $\Delta=d_{1}\geq d_{2}\geq\cdots\geq
d_{n}=\delta\geq 1$, define

$\displaystyle n_{1}=\sum_{i=1}^{n}1_{\\{d_{i}=1\\}},\quad
n_{2}=\sum_{i=1}^{n}1_{\\{d_{i}=2\\}}.$

######  Theorem 10.

Assume ${{\bf d}}$ is a graphical degree sequence with $J({\bf d})=o(M)$. Let
$c>0$ be a fixed constant.

  1. (a)

If $n_{1}=o(\sqrt{M})$ and $n_{2}=o(M)$ then a.a.s. ${\mathcal{G}}(n,{\bf d})$
is connected.

  2. (b)

If $n_{1}=\omega(\sqrt{M})$ then a.a.s. ${\mathcal{G}}(n,{\bf d})$ is
disconnected.

  3. (c)

If $n_{1}\geq c\sqrt{M}$ or $n_{2}\geq c\sqrt{M}$ then there exists
$\delta=\delta(c)>0$ such that for all sufficiently large $n$,

${\mathbb{P}}({\mathcal{G}}(n,{\bf d})\ \text{disconnected})\geq\delta.$

Since $J({\bf d})\leq\Delta^{2}$, we immediately have the following corollary.

######  Corollary 11.

Theorem 10 holds if $J({\bf d})=o(M)$ is replaced by $\Delta^{2}=o(M)$.

Next, we deal with degree sequences where $\Delta$ is rather large. Define

${\mathcal{H}}=\\{i:d_{i}\geq\sqrt{M}/\log M\\}.$

Our next result gives sufficient conditions for the connectedness of
${\mathcal{G}}(n,{\bf d})$.

######  Theorem 12.

Assume $M-2d({\mathcal{H}})=\Omega(M)$. If $n_{1}=o(\sqrt{M})$ and
$n_{2}=o(M)$ then a.a.s. ${\mathcal{G}}(n,{\bf d})$ is connected.

Conditions in Theorem 12 are not necessary. We can easily make up ${\bf d}$
where $d_{1}=n-1$, $M=\Theta(n)$ and a linear number of vertices have degree 1
(or of degree 2). Conditions in Theorem 12 are not satisfied but
${\mathcal{G}}(n,{\bf d})$ is always connected for such degree sequences.

###  1.2 Degree sequences satisfying $J({\bf d})=o(M)$

A rich family of degree sequences satisfies the condition $J({\bf d})=o(M)$
for which we may apply the probabilities in Theorems 1 and 4. For instance, it
covers all regular sublinear degree sequences, i.e. $d_{i}=d$ for all $i$ and
$d=o(n)$. We give two additional examples below that might be of interest in
applications.

  * •

$\Delta=o(n)$ and a linear (in $n$) number of vertices have degree
$\Omega(\Delta)$.

  * •

${\bf d}$ is composed of i.i.d. power-law variables of exponent $\tau>2$,
conditioned to even sum.

The reader may wonder what types of degree sequences do not satisfy $J({\bf
d})=o(M)$. Certainly, regular degree sequences with linear degrees do not
satisfy this condition. More generally, if there is a linear (in $n$) number
of vertices with degree $\Theta(n)$, then that degree sequence does not
satisfy $J({\bf d})=o(M)$.

We will prove Theorems 1 and 4 in Section 3. The proof of Theorem 9 will be
given in Section 2 and the proofs for Theorems 10 and 12 will be presented in
Section 4.

##  2 Proof of Theorem 9: chromatic number

We first briefly sketch the proof in [10]. For the upper bound, the authors
first obtained an $O(d/\ln d)$ upper bound for the multigraph $G^{*}$ from the
configuration model. A multigraph is properly coloured if every pair of
adjacent and distinct vertices are coloured differently. Only Condition (A1)
is needed for this part of the proof. Then they applied a sequence of
switching operations which repeatedly switch away the loops and multiple edges
in $G^{*}$. Then they proved that (a), every simple graph is obtained with
asymptotically the same probability after applying the switchings; (b) if $H$
is the graph induced the by set of edges added during the switchings, then
a.a.s. $\chi(H)=O(1)$. It follows immediately that a.a.s. the chromatic number
of ${\mathcal{G}}(n,{\bf d})$ is at most $\chi(G^{*})\cdot\chi(H)=O(d/\ln d)$.
Condition (A2) is needed to guarantee (a) and (b).

For the lower bound, they proved that for any partition $\sigma$ of vertices
in to $t=b\cdot d/\ln d$ parts, where $b>0$ is a sufficiently small constant,
the probability that $\sigma$ specifies a proper $t$-colouring of $G^{*}$ is
at most $t^{-2n}$. Condition (A3) was applied to obtain a lower bound on the
probability that $G^{*}$ is a simple graph. When $\Delta^{2}=o(n)$, the
probability $t^{-2n}$ is small enough to beat the union bound over all such
partitions $\sigma$, and the inverse of the probability that $G^{*}$ is
simple. Note that (A3) implies $\Delta^{2}=o(n)$.

To prove Theorem 9, we carry all analysis from [10] for $G^{*}$ to
${\mathcal{G}}(n,{\bf d})$. Both the upper and lower bound proofs for
$\chi(G^{*})$ in [10] use upper bounds on the probability of $G^{*}$
containing some set of edges $H$ where $M-2e(H)=\Omega(M)$. The upper bound of
$\chi(G^{*})$ follows by [10, Lemmas 1–3]. These lemmas hold for
${\mathcal{G}}(n,{\bf d})$ with exactly the same proofs, by applying
inequalities (1) and (4) instead of (2) and (3). The additional $1+o(1)$
factors in (1) and (4), compared with (2) and (3), do not affect the proof (in
fact, any constant factor would do). As no switching analysis is required any
more, we do not need condition (A2). Instead, we need $J({\bf d})=o(M)$ in
order to apply (1) and (4). This is guaranteed by our assumption (A1) and
$\Delta=o(n)$ as follows: by (A1), $J({\bf d})/M=O((\Delta/n)^{\alpha})$ which
is $o(1)$ if $\Delta=o(n)$.

The same translation of analysis holds for the lower bound proof. As we are
working on ${\mathcal{G}}(n,{\bf d})$ instead of $G^{*}$, it is sufficient if
the probability $t^{-2n}$ beats the union bound over the total number of such
partitions. This is always the case as there can be at most $t^{n}$ partitions
into $t$ parts. Hence, for the lower bound we do not need conditions (A3) or
$\Delta^{2}=o(n)$ any more. Instead, we impose $J({\bf d})=o(M)$ which
validates the application of the probability bounds (1) and (4).

##  3 Proofs of Theorems 1 and 4

Proof of Theorem 4.  Let $e_{1}=u_{1}v_{1},\ldots,e_{h}=u_{h}v_{h}$ be an
enumeration of the set of edges in $H_{1}$ where $h=e(H_{1})$. Let
$G_{0}=\emptyset$ and $G_{j}=G_{j-1}\cup\\{e_{j}\\}$ for every $1\leq j\leq
h$. Then,

${\mathbb{P}}\Big{(}H_{1}^{+}\mid
H_{2}^{-}\Big{)}=\prod_{j=1}^{h}{\mathbb{P}}(e_{j}\mid
G_{j-1}^{+},H_{2}^{-}).$

By Theorem 1,

$\displaystyle\prod_{j=1}^{h}{\mathbb{P}}(e_{j}\mid G_{j-1}^{+},H_{2}^{-})$
$\displaystyle\leq$
$\displaystyle\prod_{j=1}^{h}(d_{u_{j}}-d_{u_{j}}^{G_{j-1}})(d_{v_{j}}-d_{v_{j}}^{G_{j-1}})\frac{f({\bf
d},G_{j-1},H_{2})}{M-2j+2}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}(d_{i})_{d_{i}^{H_{1}}}\cdot\prod_{j=1}^{h}\frac{f({\bf
d},G_{j-1},H_{2})}{(M-2j+2)},$

where

$\displaystyle f({\bf d},G_{j-1},H_{2})$ $\displaystyle\leq$
$\displaystyle\left(1-\frac{3J({\bf
d})+\Delta(8+2\Delta(H_{2}))}{M-2j+2}-\frac{2e(H_{2})\Delta^{2}}{(M-2j+2)^{2}}\right)^{-1}$
$\displaystyle\leq$ $\displaystyle 1+\frac{6J({\bf
d})+2\Delta(8+2\Delta(H_{2}))}{M-2j+2}+\frac{4e(H_{2})\Delta^{2}}{(M-2j+2)^{2}}=1+\mathfrak{R}({\bf
d},H_{1},H_{2}),$

for every $1\leq j\leq h$. The second inequality above holds by the fact that
$(1-x)^{-1}\leq 1+2x$ for all $x\in[0,1/2]$ and the assumption that
$\mathfrak{R}({\bf d},H_{1},H_{2})\leq 1$. This yields our upper bound on
${\mathbb{P}}(H_{1}^{+}\mid H_{2}^{-})$. Again by the lower bound in Theorem
1,

$\displaystyle\prod_{j=1}^{h}{\mathbb{P}}(e_{j}\mid G_{j-1}^{+},H_{2}^{-})$
$\displaystyle\geq$
$\displaystyle\prod_{j=1}^{h}(d_{u_{j}}-d_{u_{j}}^{G_{j-1}})(d_{v_{j}}-d_{v_{j}}^{G_{j-1}})\frac{g({\bf
d},G_{j-1},H_{2})}{M-2j+2}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}(d_{i})_{d_{i}^{H_{1}}}\cdot\prod_{j=1}^{h}\frac{g({\bf
d},G_{j-1},H_{2})}{(M-2j+2)},$

where

$\displaystyle g({\bf d},G_{j-1},H_{2})$ $\displaystyle=$
$\displaystyle\left(1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta}{M-2j+2}\right)\left(1+\frac{(d_{v_{j}}-d_{v_{j}}^{G_{j-1}})(d_{u_{j}}-d_{u_{j}}^{G_{j-1}})}{M-2j+2}\right)^{-1}$
$\displaystyle\geq$ $\displaystyle 1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta+d_{v_{j}}d_{u_{j}}}{M-2j+2}\geq
1-\mathfrak{r}({\bf d},H_{1},H_{2}),$

for every $1\leq j\leq h$. The second inequality above holds by the fact that
$(1+x)^{-1}\geq 1-x$ for all $x\geq 0$. This yields our lower bound on
${\mathbb{P}}(H_{1}^{+}\mid H_{2}^{-})$.

Proof of Theorem 1.  Let ${\mathcal{G}}$ denote the set of graphs $G$ on $[n]$
with degree sequence $d_{1},\dots,d_{n}$, such that $H_{1}\subseteq G$, $G\cap
H_{2}=\emptyset$. Let $S$ denote the set of graphs in ${\mathcal{G}}$ that
contain $uv$ as an edge, and let $\overline{S}={\mathcal{G}}\setminus S$.
Then,

${\mathbb{P}}\big{(}uv\in{\mathcal{G}}(n,{\bf d})\mid
H_{1}^{+},H_{2}^{-}\big{)}=\frac{|S|}{|S|+|\overline{S}|}=\frac{1}{1+|\overline{S}|/|S|}$

We will obtain upper and lower bounds on the ratio $|\overline{S}|/|S|$ by
analysing switchings that relate graphs in $S$ to graphs in $\overline{S}$. We
first define the switching.

Given $G\in S$, a forward switching specifies an ordered $4$-tuple
$(x,a,y,b)\in[n]^{4}$ satisfying the following conditions:

  * (1)

$u,v,x,y,a,b$ are all distinct, except $x=y$ is permitted.

  * (2)

$xa$ and $yb$ are edges in $G\setminus H_{1}$.

  * (3)

None of $xu$, $yv$, and $ab$ are edges in $G\cup H_{2}$.

Then the forward switching converts $G$ to a graph $G^{\prime}\in\overline{S}$
by deleting the edges $uv$, $xa$ and $yb$ from $G$ and adding the edges $xu$,
$yv$ and $ab$. See Figure 1 for an illustration, where solid lines denote
edges in the graph and dashed lines denote non-edges.

Figure 1: Forward switching

Let $f(G)$ denote the number of forward switchings that can be applied to $G$.
We will show the following upper and lower bounds on $f(G)$:

######  Claim 13.

$\displaystyle(a)$ $\displaystyle f(G)\leq(M-2e(H_{1}))^{2}$
$\displaystyle(b)$ $\displaystyle
f(G)\geq(M-2e(H_{1}))^{2}\left(1-\frac{3J({\bf
d})+\Delta(8+d_{u}^{H_{2}}+d_{v}^{H_{2}})}{M-2e(H_{1})}-\frac{2e(H_{2})\Delta^{2}}{(M-2e(H_{1}))^{2}}\right).$

Next, given $G^{\prime}\in\overline{S}$, we count the number of forward
switchings that can produce $G^{\prime}$. In order to do so, we define a
backward switching on $G^{\prime}$ as an ordered $4$-tuple
$(x,a,y,b)\in[n]^{4}$ satisfying the following:

  * (1’)

$u,v,x,y,a,b$ are all distinct, except $x=y$ is permitted.

  * (2’)

$xa$ and $yb$ are not edges in $G^{\prime}\cup H_{2}$.

  * (3’)

$xu$, $yv$, and $ab$ are edges in $G^{\prime}\setminus H_{1}$.

Then the backward switching deletes the edges $xu$, $yv$, and $ab$, and adds
the edges $uv$, $xa$ and $yb$.

Obviously, a backward switching on $G^{\prime}$ is exactly the inverse of a
forward switching which produces $G^{\prime}$. Let $b(G^{\prime})$ be the
number of backward switchings that can be applied to $G^{\prime}$. We will
show the following.

######  Claim 14.

$\displaystyle(a)$ $\displaystyle
b(G^{\prime})\leq(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})(M-2e(H_{1}))$
$\displaystyle(b)$ $\displaystyle
b(G^{\prime})\geq(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})(M-2e(H_{1}))\left(1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta}{M-2e(H_{1})}\right).$

Let $T$ be the total number of forward switchings from $S$ to $\overline{S}$.
By definition,

$T=\sum_{G\in S}f(G)=\sum_{G^{\prime}\in\overline{S}}b(G^{\prime}).$

By Claim 13(a) and Claim 14(b),

$|\overline{S}|(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})(M-2e(H_{1}))\left(1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta}{M-2e(H_{1})}\right)\leq
T\leq|S|(M-2e(H_{1}))^{2}.$

Thus,

$\displaystyle\frac{|S|}{|S|+|\overline{S}|}$ $\displaystyle\geq$
$\displaystyle\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\left(1-\frac{2J({\bf
d})+6\Delta+2\Delta(H_{2})\Delta}{M-2e(H_{1})}\right)\left(1+\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\right)^{-1}$
$\displaystyle=$
$\displaystyle\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\cdot
g({\bf d},H_{1},H_{2}).$

Similarly, Claim 13(b) and Claim 14(a),

$\frac{|S|}{|S|+|\overline{S}|}\leq\frac{(d_{v}-d_{v}^{H_{1}})(d_{u}-d_{u}^{H_{1}})}{M-2e(H_{1})}\cdot
f({\bf d},H_{1},H_{2}).$

Hence, we have shown the upper and lower bounds of
${\mathbb{P}}(uv\in{\mathcal{G}}(n,{\bf d})\mid H_{1}^{+},H_{2}^{-})$ as
desired.

It only remains to prove the two claims. They follow from simple inclusion-
exclusion counting arguments as follows.

Proof of Claim 13.  The upper bound is obvious as there are at most
$M-2e(H_{1})$ ways to choose vertices $x$ and $a$, and then at most
$M-2e(H_{1})$ ways to choose vertices $y$ and $b$. To get the required lower
bound, we subtract from the above upper bound the number of choices where one
of the conditions in (1)–(3) is violated. If condition (1) is violated, then
$\\{x,y,a,b\\}\cap\\{u,v\\}\neq\emptyset$, or $a\in\\{y,b\\}$, or $x=b$. There
are at most $2(M-2e(H_{1}))\cdot 2\Delta\cdot
2+2\Delta(M-2e(H_{1}))+\Delta(M-2e(H_{1}))=11\Delta(M-2e(H_{1}))$ ways to
choose such 4-tuples. In our upper bound, we only considered choices where
condition (2) is satisfied. Thus, it only remains to subtract the number of
choices where condition (3) is violated. That means either (a), $xu$, $yv$, or
$ab$ is an edge in $G$; or (b), $xu$, $yv$, or $ab$ is an edge in $H_{2}$. We
call an ordered triple of vertices $(v_{1},v_{2},v_{3})$ a directed 2-path at
$v_{1}$, if both $v_{1}v_{2}$ and $v_{2}v_{3}$ are edges in the graph. Note
that for any graph $G$ with degree sequence ${\bf d}$, and any $v\in[n]$, the
number of directed 2-paths at $v$ in $G$ is always at most
$\sum_{i=1}^{\Delta}(d_{i}-1)=J({\bf d})-\Delta$. Hence, the number of choices
for (a) is at most $3(J({\bf d})-\Delta)(M-2e(H^{+}))$. The number of choices
for (b) is at most
$(d^{H_{2}}_{u}\Delta+d^{H_{2}}_{v}\Delta)(M-2e(H_{1}))+2e(H_{2})\Delta^{2}$.
These give the lower bound for $f(G)$ as desired.

Proof of Claim 14.  The upper bound is obvious. There are at most
$d_{u}-d_{u}^{H_{1}}$ ways to choose $x$, at most $d_{v}-d_{v}^{H_{1}}$ ways
to choose $y$, and at most $M-2e(H_{1})$ ways to choose $a$ and $b$. From this
upper bound, we need to subtract the number of choices where condition (1’) or
(2’) is violated (note that our choices in the upper bound guarantee condition
(3’) already). If condition (1’) is violated then
$\\{a,b\\}\cap\\{u,v,x,y\\}\neq\emptyset$. There are at most $4\cdot
2\cdot(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})\Delta$ such choices. If
condition (2’) is violated then either (a’), $xa$ or $yb$ is an edge in
$G^{\prime}$; or (b’), $xa$ or $yb$ is an edge in $H_{2}$. The number of
choices for (a’) is at most
$2(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})(J({\bf d})-\Delta)$, and the
number of choice for (b’) is at most
$2(d_{u}-d_{u}^{H_{1}})(d_{v}-d_{v}^{H_{1}})\Delta(H_{2})\Delta$. Subtracting
these upper bounds on the number of invalid choices from the upper bound on
$b(G^{\prime})$ yields the lower bound on $b(G^{\prime})$ as desired.

##  4 Proof of Theorems 10 and 12: connectivity

###  4.1 Proof techniques: the old and the new

Approximately four proof techniques or a hybrid of them have been used for
proving the connectivity of ${\mathcal{G}}(n,{\bf d})$ and for analysing
properties of ${\mathcal{G}}(n,{\bf d})$ in general, when $\Delta$ is not too
large. The first, and perhaps the most well known method uses the
configuration model. Recall that all a.a.s. results can be translated from the
configuration model to ${\mathcal{G}}(n,{\bf d})$ if ${\bf d}\in{\mathcal{D}}$
where ${\mathcal{D}}=\\{{\bf
d}:M=\Theta(n),\,\sum_{i=1}^{n}d_{i}^{2}=O(n)\\}$. Federico and Hofstad’s work
[8] is an example of this proof method. Due to the ease in handling with the
configuration model, they managed to prove more accurate result including a
critical window analysis during the connectivity phase transition, but such
distributional results cannot be directly translated to ${\mathcal{G}}(n,{\bf
d})$.

Another proof method uses graph enumeration. Assume we want to bound the
probability that $e(S,{\overline{S}})=0$. This probability is simply

$\frac{|{\mathcal{G}}(S,{\bf d}|_{S})|\cdot|{\mathcal{G}}({\overline{S}},{\bf
d}|_{{\overline{S}}})|}{|{\mathcal{G}}(n,{\bf d})|},$

where ${\bf d}|_{S}$ denotes the degree sequence obtained by restricted to
vertices in $S$, and ${\mathcal{G}}(S,{\bf d}|_{S})$ denote the set of graphs
on vertex set $S$ and with degree sequence ${\bf d}|_{S}$. Applying known
asymptotic enumeration results on $|{\mathcal{G}}(n,{\bf d})|$ one can get
asymptotic probability for the event that $e(S,{\overline{S}})$, which can
further be used to bound the probability that ${\mathcal{G}}(n,{\bf d})$ is
disconnected. This approach was taken by Wormald [24]. It may be interesting
to note that the enumeration results on which Wormald’s proof was based are by
Bender and Canfield [2], which requires $\Delta$ to be absolutely bounded.
Then Bollobás introduced the configuration model and deduced a probabilistic
proof of [2]. Afterwards the configuration model became popularised. In that
sense, Wormald’s proof can be viewed as a “detour” of the first method
aforementioned.

The third method combines the configuration model with the switching method
introduced by McKay [20, 21]. As mentioned before, a.a.s. results can be
translated from the configuration model to ${\mathcal{G}}(n,{\bf d})$ if ${\bf
d}\in{\mathcal{D}}$. What can we do for ${\bf d}\notin{\mathcal{D}}$, e.g.
when the average degree of ${\bf d}$ is growing with $n$? McKay’s switching
method starts with $G^{*}$, the multigraph produced by the configuration
model, and repeatedly switches away multiple edges in the multigraph from the
configuration model. Using simple counting argument one can show that when
$\Delta$ is below $M^{1/4}$ then the distribution of the final simple graph
obtained is very close to the uniform distribution. Then, we can deduce
properties of ${\mathcal{G}}(n,{\bf d})$ by analysing the configuration model
and the switching algorithm. There are many results of ${\mathcal{G}}(n,{\bf
d})$ obtained this way, e.g. $\chi({\mathcal{G}}(n,{\bf d}))$ in [10]
discussed in Section 2. See more examples in [15]. In terms of the
connectivity, proofs in [9, 19] followed this path.

The last method applies the switching technique directly to random graph
${\mathcal{G}}(n,{\bf d})$. Partition the set of graphs ${\mathcal{G}}(n,{\bf
d})$ into two parts $S$ and $T$ where graphs in $S$ have a certain property
${\mathcal{P}}$ and graphs in $T$ do not. Then defining switchings that relate
graphs in $S$ to graphs in $T$. By counting the number of ways to perform
switchings one can estimate the ratio $|S|/|T|$ and the probability of
property ${\mathcal{P}}$. This approach was used in [4] for the connectivity
of random $d$-regular graphs for $d$ up to $cn$ where $c$ is sufficiently
small.

In this work, we use the new tool in Corollary 5 to characterise the
connectivity phase transition for the family of degree sequences where $J({\bf
d})=o(M)$ (Theorem 10). This result is a generalisation of [8] but works for a
much larger family of degree sequences. For Theorem 12 we will use switchings
to prove that the set of edges incident with ${\mathcal{H}}$ spans a subgraph
with $O(1)$ components. Then, we expose the set of edges incident with
${\mathcal{H}}$, and then analyse the subgraph induced by
$[n]\setminus{\mathcal{H}}$. As the degrees of vertices in
$[n]\setminus{\mathcal{H}}$ are not too large, we can apply Corollary 5 again.

###  4.2 Proof of Theorem 10(b,c)

Let $Y$ denote the number of isolated edges, i.e. edges whose ends are both of
degree 1. Let $Z$ be the number of isolated triangles, i.e. triples of
vertices $\\{x,y,z\\}$ who induce a $K_{3}$ and all of the three vertices are
of degree 2. With standard first and second moment calculations using the
asymptotic probabilities in Corollary 5 we immediately have the following
lemma, whose proof we omit.

######  Lemma 15.

  * •

If $n_{1}=\Omega(\sqrt{M})$ then ${\mathbb{E}}Y\sim n_{1}^{2}/2M$ and
${\mathbb{E}}Y(Y-1)\sim n_{1}^{4}/4M^{2}$.

  * •

If $n_{2}=\Omega(M)$ then ${\mathbb{E}}Z\sim 4n_{2}^{3}/3M^{3}$ and
${\mathbb{E}}Z(Z-1)\sim 16n_{2}^{6}/9M^{6}$.

Now Theorem 10(b) follows by Chebyshev’s inequality, and Theorem 10(c) follows
by the Paley-Zygmund inequality.

###  4.3 Proof of Theorem 10(a)

######  Proposition 16.

For any ${\bf d}$ with even sum,

$|{\mathcal{G}}(n,{\bf d})|\leq\frac{M!}{2^{M/2}(M/2)!\prod_{i\in[n]}d_{i}!}.$

Proof.  Represent vertex $i$ by a bin containing exactly $d_{i}$ points. A
perfect matching over the total $M$ points in the $n$ bins is called a
pairing. A pairing produces a multigraph with degree sequence ${\bf d}$ by
representing each $\\{v(p),v(q)\\}$ as an edge where $p$ and $q$ are points
matched by the pairing and $v(p)$ and $v(q)$ are the bins/vertices that
contain points $p$ and $q$ respectively. It is easy to see that every graph in
${\mathcal{G}}(n,{\bf d})$ corresponds to exactly $\prod_{i\in[n]}d_{i}!$
pairings. On the other hand, there are exactly $M!/2^{M/2}(M/2)!$ perfect
matchings over $M$ points. The assertion follows.

Given $S\subseteq[n]$ let $X_{S}$ denote the indicator variable for the event
that $e(S,{\overline{S}})=0$. Recall that $d(S)=\sum_{i\in S}d_{i}$ and ${\bf
d}|_{S}=(d_{i})_{i\in S}$.

######  Lemma 17.

Assume $J({\bf d})=o(M)$. Suppose $S\subseteq[n]$ where $M-d(S)=\Omega(M)$.
Then,

${\mathbb{E}}X_{S}\leq(\sqrt{2}+o(1))\left(\frac{(1+o(1))d(S)}{M-d(S)}\right)^{d(S)/2}\left(1-\frac{d(S)}{M}\right)^{M/2}.$

Proof.  By Proposition 16, the number of graphs on $S$ with degree sequence
${\bf d}|_{S}$ is at most

$\frac{d(S)!}{2^{d(S)/2}(d(S)/2)!\prod_{i\in S}d_{i}!}.$

By (1),

$\displaystyle{\mathbb{E}}X_{S}$ $\displaystyle\leq$
$\displaystyle\frac{d(S)!}{2^{d(S)/2}(d(S)/2)!\prod_{i\in
S}d_{i}!}\cdot\prod_{i\in S}d_{i}!\prod_{i=1}^{d(S)/2}\frac{1+o(1)}{M-2i}$
$\displaystyle\leq$
$\displaystyle(\sqrt{2}+o(1))\frac{d(S)!}{2^{d(S)/2}(d(S)/2)!}\cdot(2+o(1))^{-d(S)/2}\frac{((M-d(S))/2)!}{(M/2)!}$
$\displaystyle\leq$
$\displaystyle(\sqrt{2}+o(1))\left(\frac{(1+o(1))d(S)}{M-d(S)}\right)^{d(S)/2}\left(1-\frac{d(S)}{M}\right)^{M/2}.~{}~{}\vrule
height=8.0pt,width=4.0pt,depth=0.0pt$

If ${\mathcal{G}}(n,{\bf d})$ is disconnected then there is a component of
${\mathcal{G}}(n,{\bf d})$ with total degree at most $M/2$. Thus, it is
sufficient to show that a.a.s. there is no $S\subseteq[n]$ where $d(S)\leq
M/2$ and $e(S,{\overline{S}})=0$. In the next lemma, we first bound the
expected number of such $S$ where $d(S)\geq 2.5|S|$.

######  Lemma 18.

A.a.s. there are no nonempty sets $S\subseteq[n]$ where $2.5|S|\leq d(S)\leq
M/2$ and $e(S,{\overline{S}})=0$.

Proof.  Let $\epsilon=0.5$. Suppose $S$ is a set of vertices with $d(S)=h\leq
M/2$ and $d(S)\geq(2+\epsilon)|S|$. Then, $|S|\leq h/(2+\epsilon)$. Hence, by
Lemma 17, for all sufficiently large $n$,

$\displaystyle\sum_{\begin{subarray}{c}S\subseteq[n]:\ d(S)=h\\\
h\geq(2+\epsilon)|S|\end{subarray}}{\mathbb{E}}X_{S}\leq
2\left(\binom{n}{h/(2+\epsilon)}1_{\\{\frac{h}{2+\epsilon}<\frac{n}{2}\\}}+2^{n}1_{\\{\frac{h}{2+\epsilon}\geq\frac{n}{2}\\}}\right)\left(\frac{(1+o(1))\rho}{1-\rho}\right)^{h/2}(1-\rho)^{M/2},$

where $\rho=h/M<1/2$. By the assumption that $n_{1}=o(\sqrt{M})$ and
$n_{2}=o(M)$, we must have $M\geq(3-o(1))n$. Thus the above is at most

$\displaystyle
2\left((2e(1+\epsilon)/3)^{2/(2+\epsilon)}\frac{\rho^{\epsilon/(2+\epsilon)}}{1-\rho}\right)^{h/2}(1-\rho)^{M/2}+2(2^{2-\epsilon/2}\rho/(1-\rho))^{h/2}(1-\rho)^{M/2}.$

We prove that

$\sum_{2\leq h\leq
M/2}\left((2e(1+\epsilon)/3)^{2/(2+\epsilon)}\frac{\rho^{\epsilon/(2+\epsilon)}}{1-\rho}\right)^{h/2}(1-\rho)^{M/2}=o(1),$

and

$\sum_{2\leq h\leq
M/2}(2^{2-\epsilon/2}\rho/(1-\rho))^{h/2}(1-\rho)^{M/2}=o(1),$

which will complete the proof of the lemma. Note that

$\displaystyle\sum_{2\leq h\leq
M/2}\left((2e(1+\epsilon)/3)^{2/(2+\epsilon)}\frac{\rho^{\epsilon/(2+\epsilon)}}{1-\rho}\right)^{h/2}(1-\rho)^{M/2}$
$\displaystyle=\sum_{2\leq h<\ln n}\Big{(}O(1)(\ln
n/M)^{\epsilon/(2+\epsilon)}\Big{)}^{h/2}+\sum_{\ln n\leq
h<0.01M}0.9^{h/2}+\sum_{0.01M\leq h\leq M/2}\exp\big{(}f(\rho)M/2\big{)},$

where

$f(\rho)=\frac{2\rho}{2+\epsilon}\ln(2e(1+\epsilon)/3)+\frac{\epsilon\rho}{2+\epsilon}\ln(\rho)+(1-\rho)\ln(1-\rho).$

The function $f(\rho)$ is below $-0.01$ uniformly over $\rho\in[0.01,0.5]$.
Hence,

$\displaystyle\sum_{2\leq h\leq
M/2}\left((2e(1+\epsilon)/3)^{2/(2+\epsilon)}\frac{\rho^{\epsilon/(2+\epsilon)}}{1-\rho}\right)^{h/2}(1-\rho)^{M/2}=o(1).$

Bounding $\sum_{2\leq h\leq
M/2}(2^{2-\epsilon/2}\rho/(1-\rho))^{h/2}(1-\rho)^{M/2}$ by $o(1)$ can be done
in a similar manner.

We are ready to complete the proof for part (a) of Theorem 10.

Proof of Theorem 10(a).  By Lemma 18 it only remains to show that a.a.s. there
are no nonempty sets $S\subseteq[n]$ where $d(S)\leq\min\\{2.5|S|,M/2\\}$ and
$e(S,{\overline{S}})=0$. Let $\xi=\xi_{n}=o(1)$ be such that
$n_{1}/\sqrt{M}\leq\xi$ and $n_{2}/M\leq\xi$. Let $S$ be a subset of vertices
with $\ell_{1}$ vertices of degree 1, $\ell_{2}$ vertices of degree 2, and
$\ell_{\geq 3}$ vertices of degree at least 3, $d(S)\leq M/2$ and $d(S)\leq
2.5|S|$. The number of ways to choose such a set $S$ is at most
$\binom{n_{1}}{\ell_{1}}\binom{n_{2}}{\ell_{2}}\binom{n}{\ell_{\geq 3}}$.
Given such an $S$, $d(S)\geq\ell_{1}+2\ell_{2}+3\ell_{\geq 3}$. It follows
immediately that

$\ell_{1}+2\ell_{2}+3\ell_{\geq 3}\leq 2.5(\ell_{1}+\ell_{2}+\ell_{\geq 3}),$

which implies that

$\ell_{\geq 3}\leq 3\ell_{1}+\ell_{2},\quad\ell_{1}+2\ell_{2}+3\ell_{\geq
3}\leq d(S)\leq 2.5(\ell_{1}+\ell_{2}+\ell_{\geq 3})\leq
10\ell_{1}+5\ell_{2}.$ (5)

In the rest of the proof, for simplicity we use $C$ to denote an absolute
positive constant, which may take different values at different places where,
the actual values of the constants do not matter. By Lemma 17, the probability
that $e(S,{\overline{S}})=0$ is at most

$\left(\frac{Cd(S)}{M}\right)^{d(S)/2}\leq\left(\frac{C(\ell_{1}+\ell_{2})}{M}\right)^{\ell_{1}/2+\ell_{2}+3\ell_{\geq
3}/2}.$

Hence, the expected number of sets $S$ where $d(S)\leq 2.5|S|$, $d(S)\leq M/2$
and $e(S,{\overline{S}})=0$ is at most

$\displaystyle\sum_{\ell_{1},\ell_{2},\ell_{\geq
3}}\binom{n_{1}}{\ell_{1}}\binom{n_{2}}{\ell_{2}}\binom{n}{\ell_{\geq
3}}\left(\frac{C(\ell_{1}+\ell_{2})}{M}\right)^{\ell_{1}/2+\ell_{2}+3\ell_{\geq
3}/2}$ $\displaystyle\hskip 14.22636pt\leq\sum_{\ell_{1},\ell_{2},\ell_{\geq
3}}\left(\frac{Cn_{1}}{\ell_{1}}\sqrt{\frac{\ell_{1}+\ell_{2}}{M}}\right)^{\ell_{1}}\left(\frac{Cn_{2}(\ell_{1}+\ell_{2})}{\ell_{2}M}\right)^{\ell_{2}}\left(\frac{Cn(\ell_{1}+\ell_{2})^{3/2}}{\ell_{\geq
3}M^{3/2}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
14.22636pt\leq\sum_{\ell_{1},\ell_{2},\ell_{\geq
3}}\left(C\xi\frac{\sqrt{\ell_{1}+\ell_{2}}}{\ell_{1}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}+\ell_{2}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C(\ell_{1}+\ell_{2})^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}.$

We split the above sum into two parts, one restricted to
$\ell_{1}\geq\ell_{2}$ and the other restricted to $\ell_{1}<\ell_{2}$, and we
show that each sum is $o(1)$. Suppose $\ell_{1}\geq\ell_{2}$. Then
$\ell_{1}+\ell_{2}\leq 2\ell_{1}$. Hence,

$\displaystyle\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}\geq\ell_{2}\end{subarray}}\left(C\xi\frac{\sqrt{\ell_{1}+\ell_{2}}}{\ell_{1}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}+\ell_{2}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C(\ell_{1}+\ell_{2})^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
14.22636pt\leq\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}\geq\ell_{2}\end{subarray}}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C\ell_{1}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}.$

Let $g(x)=(K/x)^{x}$ on $x\geq 0$ where $K>0$. By considering the derivative
of $\ln(g(x))$, it is easy to see that $g(x)$ is maximised at $x=K/e$. Thus,

$\left(C\xi\frac{\ell_{1}}{\ell_{2}}\right)^{\ell_{2}}\leq\exp\left(\frac{C\xi\ell_{1}}{e}\right),\quad\mbox{and}\quad\left(\frac{C\ell_{1}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq
3}}\leq\exp\left(\frac{C\ell_{1}^{3/2}}{e\sqrt{M}}\right).$

It follows now that

$\displaystyle\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}\geq\ell_{2}\end{subarray}}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C\ell_{1}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq
3}}=\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}\geq\ell_{2}\\\ \ell_{1}\leq M^{1/3}/\log
M\end{subarray}}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C\ell_{1}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
28.45274pt+\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}\geq\ell_{2}\\\ M^{1/3}/\log M<\ell_{1}\leq
n_{1}\end{subarray}}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C\ell_{1}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
14.22636pt\leq\sum_{\ell_{1}\leq M^{1/3}/\log
M}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\cdot\ell_{1}\exp\left(\frac{C\xi\ell_{1}}{e}\right)\cdot\sum_{\ell_{\geq
3}}\left(\frac{1}{\ell_{\geq 3}\log M}\right)^{\ell_{\geq 3}}$
$\displaystyle\hskip 28.45274pt+\sum_{M^{1/3}/\log M<\ell_{1}\leq
n_{1}}\left(\frac{C\xi}{\sqrt{\ell_{1}}}\right)^{\ell_{1}}\cdot\ell_{1}\exp\left(\frac{C\xi\ell_{1}}{e}\right)\cdot
n\exp\left(\frac{C\ell_{1}^{3/2}}{e\sqrt{M}}\right)$ $\displaystyle\hskip
14.22636pt\leq O\left(\frac{1}{\log M}\right)\sum_{\ell_{1}\leq M^{1/3}/\log
M}\ell_{1}\left(\frac{C\xi}{\sqrt{\ell_{1}}}e^{C\xi/e}\right)^{\ell_{1}}+\sum_{M^{1/3}/\log
M<\ell_{1}\leq
n_{1}}\ell_{1}n\left(\frac{C\xi}{\sqrt{\ell_{1}}}e^{C\xi/e+C\sqrt{\ell_{1}/M}}\right)^{\ell_{1}}$
$\displaystyle\hskip 14.22636pt=o(1),$

as $n_{1}=o(\sqrt{M})$.

Similarly, we have

$\displaystyle\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}<\ell_{2}\end{subarray}}\left(C\xi\frac{\sqrt{\ell_{1}+\ell_{2}}}{\ell_{1}}\right)^{\ell_{1}}\left(C\xi\frac{\ell_{1}+\ell_{2}}{\ell_{2}}\right)^{\ell_{2}}\left(\frac{C(\ell_{1}+\ell_{2})^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
14.22636pt\leq\sum_{\begin{subarray}{c}\ell_{1},\ell_{2},\ell_{\geq 3}\\\
\ell_{1}<\ell_{2}\end{subarray}}\left(\frac{C\xi\sqrt{\ell_{2}}}{\ell_{1}}\right)^{\ell_{1}}\left(C\xi\right)^{\ell_{2}}\left(\frac{C\ell_{2}^{3/2}}{\ell_{\geq
3}\sqrt{M}}\right)^{\ell_{\geq 3}}$ $\displaystyle\hskip
14.22636pt\leq\sum_{\ell_{2}\leq M^{1/3}/\log M}\ell_{2}(C\xi
e^{C\xi/\sqrt{\ell_{2}}})^{\ell_{2}}\sum_{\ell_{\geq
3}}\left(\frac{1}{\ell_{\geq 3}\log M}\right)^{\ell_{\geq
3}}+\sum_{M^{1/3}/\log M<\ell_{2}\leq n_{2}}\ell_{2}n\big{(}C\xi
e^{C\xi/\sqrt{\ell_{2}}+C\sqrt{\ell_{2}/M}}\big{)}^{\ell_{2}}$
$\displaystyle\hskip 14.22636pt=o(1),$

as $n_{2}=o(M)$. By Markov’s inequality, a.a.s. there are no sets
$S\subseteq[n]$ where $d(S)\leq 2.5|S|$, $d(S)\leq M/2$ and
$e(S,{\overline{S}})=0$. This, together with Lemma 18, completes the proof for
Theorem 10(a).

##  5 Proof of Theorem 12

We start by some structural result involving vertices in ${\mathcal{H}}$.

######  Lemma 19.

A.a.s. either all vertices in ${\mathcal{H}}$ are contained in the same
component of ${\mathcal{G}}(n,{\bf d})$, or ${\mathcal{G}}(n,{\bf d})$
contains a set of components
${\mathcal{C}}_{0},{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{k}$ for some $2\leq
k\leq\log^{7}n$, where ${\mathcal{C}}_{0}$ contains no vertex in
${\mathcal{H}}$, each ${\mathcal{C}}_{j}$ for $1\leq j\leq k$ contains at
least one vertex in ${\mathcal{H}}$, and $\cup_{j=1}^{k}{\mathcal{C}}_{j}$ has
less than $M^{3/4}$ edges.

Proof.  If $|{\mathcal{H}}|\geq\log^{7}M$ then all vertices in ${\mathcal{H}}$
are contained in the same component of ${\mathcal{G}}(n,{\bf d})$ by [16,
Lemma 28]. Suppose $|{\mathcal{H}}|<\log^{7}M$. Let ${\mathcal{C}}_{u}$ denote
the component of ${\mathcal{G}}(n,d)$ that contains $u$. We prove that a.a.s.
either all components in $\\{{\mathcal{C}}_{u},u\in{\mathcal{H}}\\}$ are of
size smaller than $M^{2/3}$, or all vertices in ${\mathcal{H}}$ are contained
in the same component of ${\mathcal{G}}(n,{\bf d})$. The proof is basically
the same as in [16, Lemma 22]. We show that a.a.s. if there is
$u\in{\mathcal{H}}$ such that $|{\mathcal{C}}_{u}|\geq M^{2/3}$ then all
vertices in ${\mathcal{H}}$ must lie in the same component. Let
$u,v\in{\mathcal{H}}$. Let ${\mathcal{G}}^{-}$ be the set of graphs in
${\mathcal{G}}(n,{\bf d})$ where ${\mathcal{C}}_{u}$ has at least $M^{2/3}$
edges and $v\notin{\mathcal{C}}_{u}$. Let ${\mathcal{G}}^{+}$ be the set of
graphs in ${\mathcal{G}}(n,{\bf d})$ where $v\in{\mathcal{C}}_{u}$. We show
that ${\mathbb{P}}({\mathcal{G}}^{-})\leq(\log
M/M^{1/6}){\mathbb{P}}({\mathcal{G}}^{+})$.

Define switchings between ${\mathcal{G}}^{-}$ and ${\mathcal{G}}^{+}$ as
follows. Let $G\in{\mathcal{G}}^{-}$. Choose a neighbour $w$ of $v$ in
${\mathcal{C}}_{v}$. Choose two vertices $(x,y)$ in ${\mathcal{C}}_{u}$ such
that $d(x,u)\leq d(y,u)$ where $d(x,u)$ denotes the graph distance between $x$
and $u$ in ${\mathcal{C}}_{u}$. Delete the edges $vw$ and $xy$ and then add
edges $xv$ and $wy$. Obviously the resulting graph $G^{\prime}$ is in
${\mathcal{G}}(n,{\bf d})$. Moreover, $u$ and $v$ lie in the same component.
There are at least $\sqrt{M}/\log M$ ways to choose $w$ since
$d_{v}\geq\sqrt{M}/\log M$. There are at least $M^{2/3}$ to choose $(x,y)$
since ${\mathcal{C}}_{u}$ has size at least $M^{2/3}$. Hence, the number of
switchings is at least $M^{7/6}/\log M$. Let $G^{\prime}\in{\mathcal{G}}^{+}$.
Note that on all shortest paths in $G^{\prime}$ between $u$ and $v$, the
neighbours of $v$ must be the same, as otherwise $G^{\prime}$ cannot be
created by a switching from some $G\in{\mathcal{G}}^{-}$. Let $P$ be such a
shortest path. Let $x$ be the neighbour of $v$ on $P$. Then there are at most
$M$ ways to choose $(y,w)$ such that an inverse switching can be applied.
Hence, the total number of inverse switchings is at most $M$. Hence,

$\frac{{\mathbb{P}}({\mathcal{G}}^{-})}{{\mathbb{P}}({\mathcal{G}}^{+})}\leq\frac{M}{M^{7/6}/\log
M}=\log M/M^{1/6}.$

Taking the union bound over all pairs of $u,v\in{\mathcal{H}}$, it follows
that a.a.s. if there is $u\in{\mathcal{H}}$ such that $|{\mathcal{C}}_{u}|\geq
M^{2/3}$ then all vertices in ${\mathcal{H}}$ must lie in the same component.
Suppose for all $u\in{\mathcal{H}}$, ${\mathcal{C}}_{u}$ has less than
$M^{2/3}$ edges then $\cup_{u\in{\mathcal{H}}}{\mathcal{C}}_{u}$ has less than
$M^{2/3}\log^{7}n<M^{3/4}$ edges. It only remains to show that a.a.s. if
$\cup_{u\in{\mathcal{H}}}{\mathcal{C}}_{u}$ has less than $M^{3/4}$ edges then
all vertices in $[n]\setminus(\cup_{u\in{\mathcal{H}}}{\mathcal{C}}_{u})$ lies
in the same component ${\mathcal{C}}_{0}$.

Condition on the set of vertices
$V^{\prime}=[n]\setminus(\cup_{u\in{\mathcal{H}}}{\mathcal{C}}_{u})$ whose
total degree $M^{\prime}$ is at least $M-2M^{3/4}$. Moreover, all vertices in
$V^{\prime}$ has degree at most $\sqrt{M}/\log M=O(\sqrt{M^{\prime}}/\log
M^{\prime})$. Let $n^{\prime}_{1}$ and $n^{\prime}_{2}$ be the number of
vertices in $V^{\prime}$ with degree one and two respectively. By the
hypothesis of Theorem 12, $n_{1}^{\prime}=o(\sqrt{M})=o(\sqrt{M^{\prime}})$
and $n_{2}^{\prime}=o(M)=o(M^{\prime})$. By Theroem 10, a.a.s. all vertices in
$V^{\prime}$ are in the same component.

######  Lemma 20.

With probability $o(1)$, ${\mathcal{G}}(n,d)$ contains a set of components
${\mathcal{C}}_{0},{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{k}$ for some $2\leq
k\leq\log^{7}n$, where ${\mathcal{C}}_{0}$ contains no vertex in
${\mathcal{H}}$, each ${\mathcal{C}}_{j}$ for $1\leq j\leq k$ contains at
least one vertex in ${\mathcal{H}}$, and $\cup_{j=1}^{k}{\mathcal{C}}_{j}$ has
less than $M^{3/4}$ edges.

Lemmas 19 and 20 immediately give the following corollary.

######  Corollary 21.

A.a.s. all vertices in ${\mathcal{H}}$ are contained in the same component of
${\mathcal{G}}(n,{\bf d})$.

Proof of Lemma 20.  Let ${\mathcal{G}}^{-}$ be the set of graphs in
${\mathcal{G}}(n,{\bf d})$ where there is a set of components
${\mathcal{C}}_{0},{\mathcal{C}}_{1},\ldots,{\mathcal{C}}_{k}$ for some $2\leq
k\leq\log^{7}n$, where ${\mathcal{C}}_{0}$ contains no vertex in
${\mathcal{H}}$, each ${\mathcal{C}}_{j}$ for $1\leq j\leq k$ contains at
least one vertex in ${\mathcal{H}}$, and $\cup_{j=1}^{k}{\mathcal{C}}_{j}$ has
less than $M^{3/4}$ edges. Fix $u\in{\mathcal{H}}$ and let ${\mathcal{G}}^{+}$
be the set of graphs in ${\mathcal{G}}(n,{\bf d})$ where $u$ is in a component
of size $\Omega(M)$. We show that
${\mathbb{P}}({\mathcal{G}}^{-})=o({\mathbb{P}}({\mathcal{G}}^{+}))$ which
then implies that ${\mathbb{P}}({\mathcal{G}}^{-})=o(1)$.

Let $G\in{\mathcal{G}}^{-}$. Let ${\mathcal{C}}_{0},\ldots,{\mathcal{C}}_{k}$
be the set of components of $G$ where ${\mathcal{C}}_{0}$ contains no vertex
in ${\mathcal{H}}$, each ${\mathcal{C}}_{j}$ for $1\leq j\leq k$ contains at
least one vertex in ${\mathcal{H}}$, and $\cup_{j=1}^{k}{\mathcal{C}}_{j}$ has
less than $M^{3/4}$ edges. Define switchings between ${\mathcal{G}}^{-}$ and
${\mathcal{G}}^{+}$ as follows. Let $v$ be a neighbour of $u$. Choose three
vertices $(w,x,y)$ in ${\mathcal{C}}_{0}$ such that $xy$ in a non-bridge edge,
and $d(x,u)\leq d(y,u)$. Replace the edges $uv$ and $xy$ by $ux$ and $yv$.
Obviously the resulting graph is in ${\mathcal{G}}^{+}$. Since
${\mathcal{C}}_{0}$ has size at least $M-M^{3/4}$, and the number of vertices
in ${\mathcal{C}}_{0}$ of degree less than 3 is $o(M)$ by the hypothesis of
Theorem 12, the number of choices for $(x,y)$ is $\Omega(M)$. The number of
choices for $v$ is at least $\sqrt{M}/\log M$. The number of vertices in
${\mathcal{C}}_{0}$ is at least $n-2M^{3/4}$ since there are at most $M^{3/4}$
edges in components other than ${\mathcal{C}}_{0}$. The number of vertices in
${\mathcal{C}}_{0}$ is also bounded from below by $(M-2M^{3/4})\log
M/\sqrt{M}\sim\sqrt{M}\log M$ since every vertex in ${\mathcal{C}}_{0}$ has
degree at most $\sqrt{M}/\log M$. Hence, the number of choices for $w$ is at
least $\varphi=\max\\{n-2M^{3/4},\frac{1}{2}\sqrt{M}\log M\\}$. Thus, the
number of switchings that can be applied to $G$ is $\Omega(M^{3/2}\varphi/\log
M)$. For $G^{\prime}\in{\mathcal{G}}^{+}$, we bound the number of inverse
switchings that can be applied to $G^{\prime}$. There are at most $n$ ways to
choose $w$. After fixing $w$, let $P$ be a shortest path from $u$ to $w$ (as
in the proof of Lemma 19 we may assume on all such shortest paths the
neighbours of $u$ are the same). Let $x$ be the neighbour of $u$ on $P$.
Finally, there are at most $M$ ways to choose the edge $vy$ so that an inverse
switching can be applied. Thus, the number of inverse switchings is at most
$nM$. Hence,

$\frac{{\mathbb{P}}({\mathcal{G}}^{-})}{{\mathbb{P}}({\mathcal{G}}^{+})}=O\left(\frac{nM}{M^{3/2}\varphi/\log
M}\right)=O\left(\frac{n\log M}{M^{1/2}\varphi}\right).$

Suppose $M\geq n^{4/3}/\log n$. Then $\varphi=\Omega(\sqrt{M}\log M)$ and thus
the above ratio of probabilities is $O(n/M)=o(1)$. Suppose $M<n^{4/3}/\log n$
then $\varphi\geq n-2M^{3/4}\sim n$ and thus the above ratio of probabilities
is $O(\log M/M^{1/2})=o(1)$. It follows now that
${\mathbb{P}}({\mathcal{G}}^{-})=o(1)$.

Now we are ready to prove the second main theorem of the paper.

Proof of Theorem 12.  Expose the set of edges incident with ${\mathcal{H}}$
and let ${\bf d}^{\prime}=(d_{i})_{i\in[n]\setminus{\mathcal{H}}}$ denote the
remaining degree sequence for vertices in $[n]\setminus{\mathcal{H}}$. That
is, $d^{\prime}_{i}=d_{i}-x_{i}$ where $x_{i}$ is the number of edges between
$i$ and ${\mathcal{H}}$. In this proof we will focus on the subgraph of
${\mathcal{G}}(n,{\bf d})$ induced by $[n]\setminus{\mathcal{H}}$.
Conditioning on ${\bf d}^{\prime}$, this subgraph is distributed as
${\mathcal{G}}([n]\setminus{\mathcal{H}},{\bf d}^{\prime})$, a uniformly
random graph on $[n]\setminus{\mathcal{H}}$ with degree sequence ${\bf
d}^{\prime}$. Note that some vertices in $[n]\setminus{\mathcal{H}}$ may have
degree 0 with respect to ${\bf d}^{\prime}$. They are not of interest for
study as they are just isolated vertices in
${\mathcal{G}}([n]\setminus{\mathcal{H}},{\bf d}^{\prime})$, and they are
known to be adjacent to some vertex in ${\mathcal{H}}$. Hence, let
$V^{\prime}$ be the set of vertices $v\in[n]\setminus{\mathcal{H}}$ where
$d^{\prime}_{v}\geq 1$. Let $M^{\prime}=\sum_{i\in V^{\prime}}d^{\prime}_{i}$.
Conditioning on $V^{\prime}$ and ${\bf d}^{\prime}$, the subgraph of
${\mathcal{G}}(n,{\bf d})$ induced by $V^{\prime}$ is distributed as
${\mathcal{G}}(V^{\prime},{\bf d}^{\prime}|_{V^{\prime}})$. By the theorem
hypothesis that $M-2d({\mathcal{H}})=\Omega(M)$, it follows that
$M^{\prime}\geq M-2d({\mathcal{H}})=\Omega(M)$. Hence, by the definition of
${\mathcal{H}}$ we have

$d^{\prime}_{i}\leq\sqrt{M}/\log M=O(\sqrt{M^{\prime}}/\log
M^{\prime}),\quad\mbox{for all $i\in V^{\prime}$.}$ (6)

######  Claim 22.

A.a.s. there exists $v\in[n]\setminus{\mathcal{H}}$ such that $d_{v}\geq 2$
and $v$ is adjacent to ${\mathcal{H}}$.

Given set $S\subseteq[n]$, we say $v$ is adjacent to $S$ if there exists $u\in
S$ which is adjacent to $v$. Next, we colour the vertices in
$[n]\setminus{\mathcal{H}}$ that are adjacent to ${\mathcal{H}}$ as follows.
Let $U$ be the set of vertices $v\in[n]\setminus{\mathcal{H}}$ where $v$ is
adjacent to some vertex in ${\mathcal{H}}$. Colour all vertices in $U$ red.
The other vertices in $n]\setminus{\mathcal{H}}$ are uncoloured. Let
$V_{1}=U\cap V^{\prime}$. I.e. $V_{1}$ is the subset of vertices in $V_{1}$
with degree at least $1$ with respect to ${\bf d}^{\prime}$. By Corollary 21,
we may assume that all red vertices are contained in the same component of
${\mathcal{G}}(n,{\bf d})$.

######  Claim 23.

A.a.s. if there is a red vertex $u$ with $d^{\prime}_{u}=0$ then
$V_{1}\neq\emptyset$.

Therefore we may assume that $V_{i}\neq\emptyset$ for all $i\in[k]$. In the
rest of the proof, we will focus on ${\mathcal{G}}(V^{\prime},{\bf
d}^{\prime}|_{V^{\prime}})$, and we call ${\bf d}^{\prime}_{v}$ the degree of
$v$ for $v\in V^{\prime}$. When we use graph notation such as $e(U,V)$ and
$d(U)$, the graph referred to is ${\mathcal{G}}(V^{\prime},{\bf
d}^{\prime}|_{V^{\prime}})$ unless otherwise specified. By construction, all
vertices in $V^{\prime}$ has degree at least 1. Moreover, by the theorem
hypothesis on $n_{1}$ and $n_{2}$ and by the facts that $n_{1}^{\prime}\leq
n_{1}$, $n_{2}^{\prime}\leq n_{2}$ and $M^{\prime}=\Omega(M)$, where
$n_{1}^{\prime}$ is the number of uncoloured vertices of degree 1 in
$V^{\prime}$, and $n_{2}^{\prime}$ is the number of uncoloured vertices of
degree 2 in $V^{\prime}$, it follows that

$n^{\prime}_{1}=o(\sqrt{M^{\prime}}),\quad n_{2}^{\prime}=o(M^{\prime}).$ (7)

Now, Theorem 12 follows from the following two claims.

######  Claim 24.

A.a.s. there is no $S\subset V^{\prime}\setminus V_{1}$ where $d(S)\leq
M^{\prime}/2$ and $e(S,V^{\prime}\setminus S)=0$.

######  Claim 25.

A.a.s. there exists no $T\subseteq[n]\setminus{\mathcal{H}}$ where
$V_{1}\subseteq T$, $d(T)\leq M^{\prime}/2$ and $e(T,V^{\prime}\setminus
T)=0$.

The proofs of Claims 24 and 25 are analogous to the proof of Theorem 10. We
briefly sketch the arguments.

Proof of Claim 24.  By (7), $n^{\prime}_{1}\leq\xi\sqrt{M^{\prime}}$, and
$n^{\prime}_{2}\leq\xi M^{\prime}$, for some $\xi=o(1)$. Moreover, by (6), the
joint probabilities in (1) can be applied to ${\mathcal{G}}(V^{\prime},{\bf
d}^{\prime}|_{V^{\prime}})$. The rest of the proof is identical to that of
Lemma 18 and Theorem 10, noting that $S$ contains only uncoloured vertices.

Proof of Claim 25.  Let $D$ denote the total degree of $V_{1}$, i.e.
$D=\sum_{u\in V_{1}}d^{\prime}_{u}$. Next, given a vector
$\ell_{1},\ell_{2},\ldots$, the number of ways to choose $T$ where
$V_{1}\subseteq T$, and there are $\ell_{i}$ uncoloured vertices of degree $i$
in $T$ is at most

$\binom{\xi\sqrt{M^{\prime}}}{\ell_{1}}\binom{\xi
M^{\prime}}{\ell_{2}}\binom{n^{\prime}}{\ell_{\geq 3}},$

where $\ell_{\geq 3}=\sum_{i\geq 3}\ell_{i}$. By Lemma 18 we may assume that

$d(T)=D+\sum_{i\geq 1}i\ell_{i}<2.5\left(\sum_{i\geq 1}\ell_{i}+D\right).$

The probability that $e(T,V^{\prime}\setminus T)=0$ is at most

$\displaystyle\left(\frac{d(T)}{M^{\prime}-d(T)}\right)^{d(T)/2}\left(1-\frac{d(T)}{M^{\prime}}\right)^{(M^{\prime}-d(T))/2}$
$\displaystyle=\left(\frac{D+\sum_{i\geq
1}i\ell_{i}}{M^{\prime}-(D+\sum_{i\geq 1}i\ell_{i})}\right)^{(D+\sum_{i\geq
1}i\ell_{i})/2}\left(1-\frac{D+\sum_{i\geq
1}i\ell_{i}}{M^{\prime}}\right)^{(M^{\prime}-(D+\sum_{i\geq 1}i\ell_{i}))/2}.$

Given $\ell_{1},\ell_{2},\ldots$, the above function is monotonely decreasing
on $D$ on the domain where $(D+\sum_{i\geq 1}i\ell_{i})/M^{\prime}\leq 1/2$.
Hence, the above probability is maximised at $D=0$. Hence, the probability of
existing such a set $T$, given $\ell_{1},\ell_{2},\ldots$, is at most

$\displaystyle\binom{\xi\sqrt{M^{\prime}}}{\ell_{1}}\binom{\xi
M^{\prime}}{\ell_{2}}\binom{n^{\prime}}{\ell_{\geq 3}}\left(\frac{\sum_{i\geq
1}i\ell_{i}}{M^{\prime}-\sum_{i\geq 1}i\ell_{i}}\right)^{\sum_{i\geq
1}i\ell_{i}/2}\left(1-\frac{\sum_{i\geq
1}i\ell_{i}}{M^{\prime}}\right)^{(M^{\prime}-\sum_{i\geq 1}i\ell_{i})/2}$
$\displaystyle\leq\binom{\xi\sqrt{M^{\prime}}}{\ell_{1}}\binom{\xi
M^{\prime}}{\ell_{2}}\binom{n^{\prime}}{\ell_{\geq 3}}\left(\frac{2\sum_{i\geq
1}i\ell_{i}}{M^{\prime}}\right)^{\sum_{i\geq 1}i\ell_{i}/2}$

where $\sum_{i\geq 1}i\ell_{i}<2.5\sum_{i\geq 1}\ell_{i}$ implying

$\ell_{\geq 3}\leq 3\ell_{1}+\ell_{2},\quad\ell_{1}+2\ell_{2}+3\ell_{\geq
3}\ell_{3}\leq 2.5(\ell_{1}+\ell_{2}+\ell_{\geq 3})\leq 10\ell_{1}+5\ell_{2}.$

The rest of the analysis is the same as in Theorem 10.

Now we prove Claims 22 and 23. Both claims concern events related to edges
incident with vertices in ${\mathcal{H}}$. We will use switchings to bound
probabilities of such events.

Proof of Claim 22.  Let ${\mathcal{E}}$ denote the event that
$e({\mathcal{H}},[n]\setminus{\mathcal{H}})>0$ and all edges between
${\mathcal{H}}$ and $[n]\setminus{\mathcal{H}}$ has one end whose degree
equals 1 in ${\mathcal{G}}(n,{\bf d})$. If there is no vertex
$v\in[n]\setminus{\mathcal{H}}$ where $d_{v}\geq 2$ and $v$ is adjacent to
${\mathcal{H}}$, then we must have either ${\mathcal{E}}$ or
$e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0$. It is then sufficient to show
that ${\mathbb{P}}({\mathcal{E}})=o(1)$ and
${\mathbb{P}}(e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0)=o(1)$. Let
${\mathcal{G}}$ be the class of graphs in ${\mathcal{G}}(n,{\bf d})$ where
$e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0$ and let
${\mathcal{G}}^{\prime}$ be the class of graphs in ${\mathcal{G}}(n,{\bf d})$
where $e({\mathcal{H}},[n]\setminus{\mathcal{H}})=2$. If
${\mathcal{G}}=\emptyset$ then
${\mathbb{P}}(e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0)=0$. Otherwise,

${\mathbb{P}}(e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0)\leq\frac{|{\mathcal{G}}|}{|{\mathcal{G}}^{\prime}|}.$

We define a switching from $G\in{\mathcal{G}}$ by choosing an edge $xy$ in
$G_{[{\mathcal{H}}]}$ and another edge $uv$ in
$G_{[[n]\setminus{\mathcal{H}}]}$. Replace these two edges by $xu$ and $yv$.
The resulting graph $G^{\prime}$ is in ${\mathcal{G}}^{\prime}$. There are
$d({\mathcal{H}})/2=\Omega(\sqrt{M}/\log M)$ ways to choose $xy$ and
$d([n]\setminus{\mathcal{H}})=\Omega(M)$ ways to choose $uv$. So the number of
switchings applicable on $G$ is at least $\Omega(M^{3/2}/\log M)$. On the
other hand, for every $G^{\prime}$, it can be produced by at most 1 way, as
there are exactly 2 edges between ${\mathcal{H}}$ and
$[n]\setminus{\mathcal{H}}$. It follows then that

${\mathbb{P}}(e({\mathcal{H}},[n]\setminus{\mathcal{H}})=0)\leq\frac{|{\mathcal{G}}|}{|{\mathcal{G}}^{\prime}|}=O(\log
M/M^{3/2}),$

as desired.

Next, let ${\mathcal{G}}$ be the class of graphs in ${\mathcal{G}}(n,{\bf
d})\cap{\mathcal{E}}$, and let ${\mathcal{G}}^{\prime}$ be the class of graphs
in ${\mathcal{G}}(n,{\bf d})$ where there is exactly one neighbour of
${\mathcal{H}}$ in $[n]\setminus{\mathcal{H}}$ with degree at least 2, and all
the other neighbours of ${\mathcal{H}}$ in $[n]\setminus{\mathcal{H}}$ have
degree equal to 1. Define a switching from ${\mathcal{G}}$ to
${\mathcal{G}}^{\prime}$ as follows. Given $G\in{\mathcal{G}}$, choose 4
vertices $(u,v,x,y)$ such that $u\in{\mathcal{H}}$,
$v,x,y\in[n]\setminus{\mathcal{H}}$, $uv$ and $xy$ are edges, and $d_{x}\geq
2$. Since $d_{x}>1$ and $d_{v}=1$ it follows immediately that $ux$ and $vy$
are not edges. The switching replaces $uv$ and $xy$ by $ux$ and $vy$. The
resulting graph $G^{\prime}$ is in ${\mathcal{G}}^{\prime}$ since $x$ becomes
a neighbour of ${\mathcal{H}}$ and $d_{x}\geq 2$. There is at least one way to
choose $v$, since $G\in{\mathcal{E}}$. The total degree of
$[n]\setminus{\mathcal{H}}$ is $\Omega(M)$ by the theorem assumption, and
there are at most $o(\sqrt{M})$ vertices in the set whose degree is 1.
Moreover, all vertices in $[n]\setminus{\mathcal{H}}$ has degree at most
$\sqrt{M}/\log M$. Hence, there are at least $\Omega(M)/(\sqrt{M}/\log
M)=\Omega(\sqrt{M}\log M)$ vertices in $[n]\setminus{\mathcal{H}}$ whose
degree is at least 2. Hence, the number of choices for $x$ and $y$ is
$\Omega(\sqrt{M}\log M)$. Thus, the number of switchings that can be applied
to $G$ is $\Omega(\sqrt{M}\log M)$. On the other hand, given
$G^{\prime}\in{\mathcal{G}}$, there is a unique way to choose $u$ and $x$, and
at most $n_{1}$ ways to choose $v$ and $y$ so that an inverse switching can be
applied. Thus,

${\mathbb{P}}({\mathcal{E}})=O\left(\frac{n_{1}}{\sqrt{M}\log M}\right)=o(1),$

and our assertion follows.

Proof of Claim 23.  Let ${\mathcal{P}}$ denote the set of graphs in
${\mathcal{G}}(n,{\bf d})$ with the property in Claim 22, i.e. there exists
$v\in[n]\setminus{\mathcal{H}}$ where $d_{v}\geq 2$ and $v$ is adjacent to
${\mathcal{H}}$. Let ${\mathcal{G}}$ denote the set of graphs in
${\mathcal{P}}$ where for all $v\in[n]\setminus{\mathcal{H}}$ adjacent to
${\mathcal{H}}$, $d^{\prime}_{u}=0$. Let ${\mathcal{G}}^{\prime}$ be the set
of graphs in ${\mathcal{P}}$ where there are exactly two vertices
$v_{1},v_{2}\in[n]\setminus{\mathcal{H}}^{\prime}$ such that
$d^{\prime}_{v_{1}}=1$, $d^{\prime}_{v_{2}}\geq 1$, and $d^{\prime}_{v}=0$ for
all $v\in([n]\setminus{\mathcal{H}})\setminus\\{v_{1},v_{2}\\}$. Define a
switching from ${\mathcal{G}}$ to ${\mathcal{G}}^{\prime}$ as follows. Given
$G\in{\mathcal{G}}$, the switching chooses 4 vertices $(u,v,x,y)$ such that
$u\in{\mathcal{H}}$, $v,x,y\in[n]\setminus{\mathcal{H}}$, $uv$ and $xy$ are
edges, $d_{v}\geq 2$ and $d^{\prime}_{x}\geq 2$. Since $d^{\prime}_{x}>0$ and
$d^{\prime}_{v}=0$, we know that $ux$ and $vy$ are not edges. The switching
replaces edges $uv$ and $xy$ by $ux$ and $vy$. Let $G^{\prime}$ denote the
resulting graph. In $G^{\prime}$, both $x$ and $v$ are adjacent to
${\mathcal{H}}$, since $x$ is adjacent to $u\in{\mathcal{H}}$, and $v$ is
adjacent to some vertex $u^{\prime}\in{\mathcal{H}}$ where $u^{\prime}\neq u$,
as $d_{v}\geq 2$ and $d^{\prime}_{v}$ was equal to 0 in $G$. Let $U^{\prime}$
be the set of uncoloured vertices. The total degree of $U^{\prime}$ is at
least $M^{\prime}=\Omega(M)$, since $e(U^{\prime},[n]\setminus U^{\prime})=0$
in $G$ by the definition of ${\mathcal{G}}$. Moreover, there are at most
$o(\sqrt{M})$ vertices in $U^{\prime}$ of degree one by (7). Thus, the number
of choices for $x$ and $y$ is at least $\Omega(M)-o(\sqrt{M})=\Omega(M)$.
Consequently, the total number of ways to perform a switching on $G$ is at
least $\Omega(M)$. On the other hand, given
$G^{\prime}\in{\mathcal{G}}^{\prime}$, there are exactly 2 vertices in
$[n]\setminus{\mathcal{H}}$ whose degrees (with respect to ${\bf d}^{\prime}$)
are at least 1, and they must be $v$ (the one with degree equal to 1) and $x$.
Fixing $v$ fixes $y$ as $d^{\prime}_{v}=1$. Given $x$ there are at most
$\sqrt{M}/\log M$ ways to choose $u$ as $d_{x}\leq\sqrt{M}/\log M$. Hence, the
number of ways $G^{\prime}$ can be created via a switching is at most
$2\sqrt{M}/\log M$. Together with Claim 22,

${\mathbb{P}}(V_{1}=\emptyset)\leq\frac{|{\mathcal{G}}|}{|{\mathcal{G}}^{\prime}|}+{\mathbb{P}}(\neg{\mathcal{P}})\leq\frac{2\sqrt{M}/\log
M}{\Omega(M)}+o(1)=o(1).$

This completes the proof of the claim.

## References

  * [1] Alexander Barvinok and John A Hartigan.  The number of graphs and a random graph with a given degree sequence.  Random Structures & Algorithms, 42(3):301–348, 2013.
  * [2] Edward A Bender and E Rodney Canfield.  The asymptotic number of labeled graphs with given degree sequences.  Journal of Combinatorial Theory, Series A, 24(3):296–307, 1978\.
  * [3] Béla Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  European Journal of Combinatorics, 1(4):311–316, 1980.
  * [4] Colin Cooper, Alan Frieze, and Bruce Reed.  Random regular graphs of non-constant degree: connectivity and hamiltonicity.  Combinatorics, Probability & Computing, 11(3):249, 2002.
  * [5] Colin Cooper, Alan Frieze, Bruce Reed, and Oliver Riordan.  Random regular graphs of non-constant degree: Independence and chromatic number.  Combinatorics Probability and Computing, 11(4):323–341, 2002.
  * [6] Paul Erdős and Alfréd Rényi.  On the strength of connectedness of a random graph.  Acta Mathematica Academiae Scientiarum Hungarica, 12(1-2):261–267, 1964.
  * [7] Alberto Espuny Díaz, Felix Joos, Daniela Kühn, and Deryk Osthus.  Edge correlations in random regular hypergraphs and applications to subgraph testing.  SIAM Journal on Discrete Mathematics, 33(4):1837–1863, 2019.
  * [8] Lorenzo Federico and Remco Van der Hofstad.  Critical window for connectivity in the configuration model.  Combinatorics, Probability and Computing, 26(5):660–680, 2017.
  * [9] Alan Frieze.  On random regular graphs with non-constant degree.  Carnegie Mellon University, Department of Mathematics, 1988.
  * [10] Alan Frieze, Michael Krivelevich, and Cliff Smyth.  On the chromatic number of random graphs with a fixed degree sequence.  Combinatorics Probability and Computing, 16(5):733, 2007.
  * [11] Alan M Frieze and T Łuczak.  On the independence and chromatic numbers of random regular graphs.  Journal of Combinatorial Theory, Series B, 54(1):123–132, 1992\.
  * [12] Pu Gao, Mikhail Isaev, and Brendan D McKay.  Sandwiching random regular graphs between binomial random graphs.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 690–701. SIAM, 2020.
  * [13] Pu Gao, Remco van der Hofstad, Angus Southwell, and Clara Stegehuis.  Counting triangles in power-law uniform random graphs.  arXiv preprint arXiv:1812.04289, 2018.
  * [14] Mikhail Isaev and Brendan D McKay.  Complex martingales and asymptotic enumeration.  Random Structures & Algorithms, 52(4):617–661, 2018.
  * [15] Svante Janson.  Random graphs with given vertex degrees and switchings.  Random Structures & Algorithms, 2019.
  * [16] 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-2):263–310, 2018.
  * [17] Jeong Han Kim, Benny Sudakov, and Van Vu.  Small subgraphs of random regular graphs.  Discrete Mathematics, 307(15):1961–1967, 2007.
  * [18] Michael Krivelevich, Benny Sudakov, Van H Vu, and Nicholas C Wormald.  Random regular graphs of high degree.  Random Structures & Algorithms, 18(4):346–363, 2001.
  * [19] Tomasz Luczak.  Sparse random graphs with a given degree sequence.  In Proceedings of the Symposium on Random Graphs, Poznan, pages 165–182, 1989.
  * [20] Brendan D McKay.  Subgraphs of random graphs with specified degrees.  1981\.
  * [21] Brendan D McKay.  Asymptotics for 0-1 matrices with prescribed line sums.  Enumeration and Design,(Academic Press, 1984), pages 225–238, 1984\.
  * [22] Brendan D McKay.  Subgraphs of dense random graphs with specified degrees.  arXiv preprint arXiv:1002.3018, 2010.
  * [23] Michael Molloy and Bruce Reed.  The size of the giant component of a random graph with a given degree sequence.  Combinatorics probability and computing, 7(3):295–305, 1998.
  * [24] Nicholas C Wormald.  The asymptotic connectivity of labelled regular graphs.  Journal of Combinatorial Theory, Series B, 31(2):156–167, 1981\.