# Fully graphic degree sequences and P-stable degree sequences111The authors
thank to Gábor Lippner the interesting discussions about the topic

Péter L. Erdős222The authors were supported in part by NKFIH grant SNN 135643,
K 132696 István Miklós333The authors were supported in part by NKFIH grant SNN
135643, K 132696 Lajos Soukup444LS was supported in part by NKFIH grant K
129211. HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda u 13–15
Budapest, 1053 Hungary
<EMAIL_ADDRESS>
###### Abstract

The notion of $P$-stability played an influential role in approximating the
permanents, sampling rapidly the realizations of graphic degree sequences, or
even studying and improving network privacy. However, we did not have a good
insight of the structure of $P$-stable degree sequence families. In this paper
we develop a remedy to overstep this deficiency.

We will show, that if an infinite set of graphic degree sequences,
characterized by some simple inequalities of their fundamental parameters, is
$P$-stable, then it is “fully graphic” – meaning that every degree sequence
with an even sum, meeting the specified inequalities, is graphic. The reverse
statement also holds: an infinite, fully graphic set of degree sequences
characterized by some simple inequalities of their fundamental parameters is
$P$-stable.

Along the way, we will significantly strengthen some well-known, older
results, and we construct new P-stable families of degree sequences.

###### keywords:

fully graphic degree sequences, simple degree sequence region, $P$-stable
degree sequences, switch Markov chain

##  1 Introduction

In this paper we explore the connection between P-stability and the “fully
graphic” property of specific regions of degree sequences, establishing a
close relationship between these concepts.

We start the section with recalling and introducing some notions and
notations. If $n>c_{1}\geq c_{2}$ and $\Sigma$ are natural numbers with
$n\cdot c_{1}\geq\Sigma\geq n\cdot c_{2}$, let

$\displaystyle\operatorname{\mathbb{D}}(n,c_{1},c_{2})=\\{(d_{1},\dots,d_{n})\in\mathbb{N}^{n}:c_{1}\geq
d_{1}\geq\dots\geq d_{n}\geq c_{2},\textstyle\sum_{i=1}^{n}d_{i}\text{ is
even}\\},$
$\displaystyle\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})=\\{(d_{1},\dots,d_{n})\in\operatorname{\mathbb{D}}(n,c_{1},c_{2}):\
\textstyle\sum_{i=1}^{n}d_{i}=\Sigma\\}.$

We say that a collection $\mathbb{D}$ of degree sequences is a simple degree
sequence region iff there exists a property $\varphi(n,\Sigma,c_{1},c_{2})$
such that

$\mathbb{D}=\mathbb{D}[\varphi]\coloneqq\bigcup\left\\{\mathbb{D}(n,\Sigma,c_{1},c_{2})\
:\ n>c_{1}\geq c_{2}\text{ and }\varphi(n,\Sigma,c_{1},c_{2})\text{
holds}\right\\}.$ (SR)

Similarly, we say that a collection $\mathbb{D}$ of degree sequences is a very
simple degree sequence region iff there exists a property
$\psi(n,c_{1},c_{2})$ such that

$\mathbb{D}=\mathbb{D}[\psi]\coloneqq\bigcup\left\\{\mathbb{D}(n,c_{1},c_{2})\
:\ n>c_{1}\geq c_{2}\text{ and }\psi(n,c_{1},c_{2})\text{ holds}\right\\}.$
(VSR)

We will use the expression (very) simple region for short.

A (very) simple region $\mathbb{D}$ will be called fully graphic iff every
degree sequence from the region is graphic. $\mathbb{D}$ is almost fully
graphic iff $\mathbb{D}\setminus\mathcal{D}$ is fully graphic for some finite
$\mathcal{D}$.

Given a graphic degree sequence ${D}$ of length $n$ let

$\partial({D})=\sum_{1\leq i<j\leq
n}{|\mathcal{G}({D}+1^{-i}_{-j})|}/{|\mathcal{G}({D})|}.$ (1)

where the vector $1^{-i}_{-j}$ is comprised of all zeros, except at the $i$th
and $j$th coordinates, where the values are $-1$. The operation
$D\mapsto{D}+1^{-i}_{-j}$ is called a _perturbation operation_ on the degree
sequences. We define two more similar operations: $D+1^{-i}_{+j}$ and
$D+1^{+i}_{+j}$ analogously. Let us emphasize that we do not assume that $i$
and $j$ are different, so for example the operation $D+1^{+j}_{+j}$ is also
defined, and it adds 2 to the $j^{th}$ coordinate.

We say that a family $\mathbb{D}$ of degree sequences is P-stable if there is
a polynomial $p(n)$ such that $\partial({D})\leq p(|{D}|)$ for each graphic
element $D$ of $\mathbb{D}$. Let us emphasize that we do not require every
element of a P-stable family to be graphic. The P-stability has alternative,
but equivalent definitions using different perturbation operations. In the
Appendix of this paper, we describe a short history of these definitions, and
prove their equivalence.

The P-stability of an infinite family of degree sequences is an important
property. It would be enough to mention one result: the switch Markov Chain
process rapidly mixes on P-stable families (see [5, Theorems 8.3]). But that
P-stability plays an influential role in approximating the permanents, and
even studying and improving network privacy.

Determining whether a particular family is P-stable is typically challenging.
There exist only a few results establishing the P-stability of families of
degree sequences for simple graphs. First, we examine three of them which
implicitly considered simple and very simple regions.

  1. (P1)

(Jerrum, McKay, Sinclair [11]) The very simple degree sequence region
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]$ is P-stable,
where
$\varphi_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}\equiv(c_{1}-c_{2}+1)^{2}\leq
4c_{2}(n-c_{1}-1)$.

  2. (P2)

(Greenhill, Sfragara [9]) The simple degree sequence region
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{GS}}]$ is P-stable, where
$\varphi_{\rule{0.0pt}{4.52083pt}\\!{GS}}\equiv(2\leq c_{2}\text{ and }3\leq
c_{1}\leq\sqrt{\Sigma/9})$. (This result was not announced explicitly, but [9,
Lemma 2.5] clearly proved this fact.)

  3. (P3)

(Jerrum, McKay, Sinclair [11]) The simple degree sequence region
$\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$ is P-stable, where
${\varphi^{*}_{J\\!M\\!S}}\equiv(\Sigma-
nc_{2})(nc_{1}-\Sigma)\leq(c_{1}-c_{2})\left\\{(\Sigma-
nc_{2})(n-c_{1}-1)+(nc_{1}-\Sigma)c_{2}\right\\}.$

In contrast with P-stability, the classical theorem of Paul Erdős and Gallai
([3]) makes easy to check if a certain sequence is graphic or not. As an
extension of this result, in Section 2 we show that every simple region
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ contains exactly one
primitive element, (i.e.a sequence in the form
$(c_{1},\dots,c_{1},a,c_{2},\dots c_{2})$), and the region
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ is fully graphic iff its
primitive element is graphic (see Theorem 2.5).

So we have established a machinery to decide whether certain (very) simple
regions are fully graphic or not. Using that machinery, in Theorems 3.1, 3.4
and 3.6 we show the following

  1. (P1∗)

The very simple region
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]$ is fully
graphic.

  2. (P2∗)

The simple region $\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{GS}}]$ is
fully graphic.

  3. (P3∗)

The simple region $\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$ is fully graphic.

When comparing statements (P1) and (P2) with their counterparts (P1∗) and
(P2∗), a fundamental question arises, serving as the central focus of this
paper: “What is the connection between P-stability and the fully graphic
property of specific (very) simple regions?”

Concerning the “fully graphic $\longrightarrow$ P-stable” direction, if we
consider very simple regions, then we can prove the following strengthening of
(P1) which is actually the strongest possible result (Theorem 4.2):

######  Theorem.

The largest fully graphic very simple region

$\mathbb{D}_{\max}\coloneqq\bigcup\\{\operatorname{\mathbb{D}}(n,c_{1},c_{2}):\text{
$\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ is fully graphic}\\}$

is $P$-stable, and so the switch Markov chain is rapidly mixing on
$\mathbb{D}_{\max}$.

We do not know whether a similar statement holds for simple regions.

######  Problem 1.1.

Is it true that the largest fully graphic simple region

$\mathbb{D}^{\prime}=\bigcup\\{\operatorname{\mathbb{D}}(n,\Sigma,c_{2},c_{1}):\text{
$\operatorname{\mathbb{D}}(n,\Sigma,c_{2},c_{1})$ is fully graphic}\\}$

is $P$-stable?

Concerning the “P-stable $\longrightarrow$ fully graphic ” direction, we have
partial result claiming that a P-stable very simple region should contain
large fully graphic very simple regions provided the region satisfies some
natural restrictions. To formulate our result precisely, let us say that a
very simple region $\mathbb{D}$ is a cone region iff for some functions
$f,g\in\mathbb{N}^{\mathbb{N}}$ we have

$\mathbb{D}=\mathbb{D}(f,g)\coloneqq\bigcup\\{\operatorname{\mathbb{D}}(n,g(n),f(n)):n\in\mathbb{N}\\}.$

In Section 5 we prove the following results (Theorem 5.10 and Corollary 5.11)

######  Theorem.

Assume that $f,g,h\in\mathbb{N}^{\mathbb{N}}$ are increasing functions . If
the cone region $\mathbb{D}(f,g)$ is P-stable, then $\mathbb{D}(f+h,g-h)$ is
almost fully graphic provided

  1. (1)

$f(n+k)\leq f(n)+k$ for each $n,k\in\mathbb{N}$,

  2. (2)

$lim_{n\to\infty}h(n)/\ln(n)=\infty$.

######  Corollary.

Assume that
$0\leq{\varepsilon}_{2}<{\varepsilon}^{\prime}_{2}<{\varepsilon}^{\prime}_{1}<{\varepsilon}_{1}\leq
1$. If the very simple region
$\mathbb{D}\coloneqq\bigcup_{n\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n,\lfloor{\varepsilon}_{1}\cdot
n\rfloor,\lceil{\varepsilon}_{2}\cdot n\rceil)$ is P-stable, then the region
$\mathbb{D}^{\prime}=\bigcup_{n\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n,\lfloor{\varepsilon}^{\prime}_{1}\cdot
n\rfloor,\lceil{\varepsilon}^{\prime}_{2}\cdot n\rceil)$ is almost fully
graphic.

The proof of the previous theorem is based some observations concerning split
graphs and Tyshkevich product.

In Section 4, besides proving that the largest graphic very simple region is
P-stable, we also construct new P-stable simple regions. To do so we should
improve a method which was developed in [11] to prove (P1). In [11] to obtain
(P1) the authors actually prove that $\partial({D})\leq n^{10}$ for each
${{D}}\in\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ provided
${\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}(n,c_{1},c_{2})$ holds.
Using a finer analysis we can estimate $\partial({D})$ for a single degree
sequence under milder assumptions. Namely, we will prove the following
statement (Theorem 4.4):

######  Theorem.

If a graphic degree sequence ${D}=(d_{1},d_{2},\dots,d_{n})$ satisfies

$\forall k\in[1,n]\quad\sum_{i=1}^{k}d_{i}\leq k\cdot(k-1)+d_{n}\cdot(n-k)+1,$
(45)

then $\partial({D})\leq 3\cdot n^{9}$.

In [11] the authors prove that
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]\subset\mathbb{D}_{\varphi^{*}_{J\\!M\\!S}}$,
i.e. (P3) is a stronger statement than (P1). However, the following result
(Theorem 4.8) show (P3) does not yield Theorem 4.4:

######  Theorem.

The simple region

$\mathbb{D}_{0}=\bigcup\\{\operatorname{\mathbb{D}}(2m,4m,m,1):m\geq 4\\}$ (2)

is fully graphic and P-stable, but
$\mathbb{D}_{0}\cap\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]=\emptyset$.

##  2 Characterization of fully graphic regions
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$

In this section we study fully graphic simple degree sequence regions.

######  Definition 2.1.

A non-increasing sequence $(d_{1},\dots,d_{n})$ has the Erdős-Gallai property
if and only if for each $1\leq k\leq n$,

$\sum_{i=1}^{k}d_{i}\leq k(k-1)+\sum_{i=k+1}^{n}\min(d_{i},k).$

The next statement is almost trivial, but will be very convenient later on.

######  Proposition 2.2.

For all $D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$, property (2.1)
holds for each $k\leq c_{2}$ and $k>c_{1}$.

###### Proof.

When $k\leq c_{2}$ then

$\sum_{i=1}^{k}d_{i}\leq kc_{1}\leq k(n-1)=k(k-1)+(n-k)k.$

If $k>c_{1}$ then $kc_{1}\leq k(k-1).$ ∎

We denote by $(a)_{m}$ the constant $a$ sequence of length $m$.

######  Definition 2.3.

If $n>c_{1}\geq c_{2}$ are natural numbers, we say that a sequence
$D=(d_{1},\dots,d_{n})\in\operatorname{\mathbb{D}}(n,c_{1},c_{2},$) is
primitive if and only if $D$ has the form

$D=\underbrace{c_{1},\ldots,c_{1}}_{k},a,\underbrace{c_{2},\ldots,c_{2}}_{(n-1)-k},$
(2)

for some $1\leq k\leq n$ and $c_{2}\leq a\leq c_{1}$.

######  Definition 2.4.

If $n>c_{1}\geq c_{2}$ and $\Sigma$ are natural numbers with $n\cdot
c_{1}\geq\Sigma\geq n\cdot c_{2}$, we define the _least Erdős-Gallai sequence
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ of length $n$ with the given sum
$\Sigma$ and with given maximum and minimum elements $c_{1}$ and $c_{2}$_ as
follows:

$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})=\underbrace{c_{1},\ldots,c_{1}}_{\alpha},a,\underbrace{c_{2},\ldots,c_{2}}_{(n-1)-\alpha},$
(3)

where

$\alpha=\left\lfloor\frac{\Sigma-n\cdot c_{2}}{c_{1}-c_{2}}\right\rfloor$ (4)

and

$a=\Sigma-({\alpha}\cdot c_{1}+(n-1-{\alpha})\cdot c_{2}).$ (5)

######  Theorem 2.5.

Assume that $n>c_{1}\geq c_{2}$ and $\Sigma$ are natural numbers with $n\cdot
c_{1}\geq\Sigma\geq n\cdot c_{2}$.

  1. (1)

$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$
and is primitive.

  2. (2)

If $\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is Erdős-Gallai, then every
element of $\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ is Erdős-Gallai.

###### Proof of Theorem 2.5 (1).

Clearly, $\sum\operatorname{LEG}(n,\Sigma,c_{1},c_{2})=\Sigma,$ and
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is primitive by its definition.

Since ${\alpha}\cdot c_{1}+(n-1-{\alpha})\cdot
c_{2}={\alpha}\cdot(c_{1}-c_{2})+(n-1)\cdot c_{2}$, we have

$a\geq\Sigma-\frac{\Sigma-n\cdot c_{2}}{(c_{1}-c_{2})}(c_{1}-c_{2})+(n-1)\cdot
c_{2}=c_{2}.$ (6)

Moreover, $({\Sigma-n\cdot c_{2}})/{(c_{1}-c_{2})}-1<{\alpha}$, hence

$\displaystyle a=\Sigma$ $\displaystyle-({\alpha}\cdot(c_{1}-c_{2})+(n-1)\cdot
c_{2})\leq$ $\displaystyle\leq\Sigma-\left(\left(\frac{\Sigma-n\cdot
c_{2}}{c_{1}-c_{2}}-1\right)\cdot(c_{1}-c_{2})\right)+(n-1)\cdot c_{2}=c_{1}.$
(7)

Putting together (6) and (7), we obtain $c_{1}\geq a\geq c_{2}$. So
$\operatorname{LEG}(n,c_{1},c_{2},\Sigma)$ is really an element of
$\operatorname{\mathbb{D}}(n,c_{1},c_{2})$. ∎

Before proving Theorem 2.5 (2), we need some preparation. Denote
$\operatorname{\triangleleft_{lex}}$ the lexicographical order on finite
sequences (i.e.
$(d_{1},\dots,d_{n})\operatorname{\triangleleft_{lex}}(e_{1},\dots,e_{n})$ iff
$d_{j}<e_{j}$, where $j=\min\\{i:d_{i}\neq e_{i}\\}$).

######  Lemma 2.6.

Assume that
$D=(d_{1},\dots,d_{n})\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$, and
$1\leq\ell<m\leq n$ with $d_{\ell}<c_{1}$ and $d_{m}>c_{2}$. Write
$D^{\prime}=D+1^{+\ell}_{-m}$.

  1. (1)

$D^{\prime}\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ and
$D\operatorname{\triangleleft_{lex}}D^{\prime}$.

  2. (2)

If $D^{\prime}$ is Erdős-Gallai, then so is $D$.

###### Proof.

(1) It is trivial from the construction.

(2) Assume that (2.1) fails for $D$:
$\qquad\displaystyle\sum_{i=1}^{k}d_{i}>k(k-1)+\sum_{i=k+1}^{n}\min(d_{i},k).$
We will show that (2.1) fails for $D^{\prime}$. We should distinguish three
cases:

Case 1. $k<\ell.$

If $\min(k,d_{\ell})<\min(k,d^{\prime}_{\ell})$, then
$\min(k,d_{\ell})+1=\min(k,d_{\ell}+1)$, and so $d_{\ell}<k$. Hence,
$\min(d^{\prime}_{m},k)=\min(d_{m}-1,k)=d_{m}-1$. Thus,
$\min(k,d^{\prime}_{\ell})+\min(k,d^{\prime}_{m})=\min(k,d_{\ell})+\min(k,d_{m})$.

If $\min(k,d_{\ell})=\min(k,d^{\prime}_{\ell})$, then
$\min(k,d^{\prime}_{\ell})+\min(k,d^{\prime}_{m})\leq\min(k,d_{\ell})+\min(k,d_{m})$.
Thus,
$\sum_{i=k+1}^{n}\min(k,d_{i})\geq\sum_{i=k+1}^{n}\min(k,d^{\prime}_{i})$, and
so

$\sum_{i=1}^{k}d^{\prime}_{i}=\sum_{i=1}^{k}{d_{i}}>k(k-1)+\sum_{i=k+1}\min(k,d_{i})\geq
k(k-1)+\sum_{i=k+1}\min(k,d^{\prime}_{i}).$ (8)

Case 2. $\ell\leq k<m$.

Then $d_{i}^{\prime}\geq d_{i}$ for $i\leq k$ and $d^{\prime}_{i}\leq d_{i}$
for $k+1\leq i\leq n$, so

$\sum_{i=1}^{k}d^{\prime}_{i}\geq\sum_{i=1}^{k}{d_{i}}>k(k-1)+\sum_{i=k+1}\min(k,d_{i})\geq
k(k-1)+\sum_{i=k+1}\min(k,d^{\prime}_{i}).$ (9)

Case 3. $m\leq k$.

Since $\ell<m$, $d^{\prime}_{\ell}=d_{\ell}+1$ and $d^{\prime}_{m}=d_{m}-1$,
we have
$\sum_{i=1}^{k}d^{\prime}_{i}=\sum_{i=1}^{k}d_{i}+1-1=\sum_{i=1}^{k}d_{i}$.
Moreover, $d_{i}^{\prime}=d_{i}$ for $k+1\leq i\leq n$. Thus

$\sum_{i=1}^{k}d^{\prime}_{i}=\sum_{i=1}^{k}{d_{i}}>k(k-1)+\sum_{i=k+1}\min(k,d_{i})=k(k-1)+\sum_{i=k+1}\min(k,d^{\prime}_{i}).$
(10)

Hence, (2.1) really fails for $D^{\prime}$. ∎

######  Lemma 2.7.

$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ contains just one primitive
element, $\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$, which is the
$\operatorname{\triangleleft_{lex}}$-maximal element of
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$.

###### Proof.

We know that $\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is a primitive element
of $\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ by Theorem 2.5 (1).
Observe now that $\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ can not
contain two different primitive elements.

Indeed, assume that $A=(c_{1})_{k}a(c_{2})_{n-k-1}$ and
$B=(c_{1})_{\ell}b(c_{2})_{n-\ell-1}$ are from
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$. If $\Sigma=c_{1}\cdot n$,
then $\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ contains just one
element: the $(c_{1})_{n}$ sequence. So we can assume that $\Sigma<n\cdot
c_{1}$, and so we can assume that $a,b<c_{1}$.

If $k=\ell$, then $a=\Sigma-(kc_{1}+(n-k-1)c_{2})=\Sigma-(\ell
c_{1}+(n-\ell-1)c_{2})=b$, so the two sequences are the same. Assume that
$k<\ell$. Using that $a<c_{1}$, we obtain

$\sum A=kc_{1}+a+(n-k-1)c_{2}<(k+1)c_{1}+(n-k-1)c_{2}\leq\ell
c_{1}+b+(n-\ell-1)c_{2}=\sum B,$ (11)

contradiction. We proved the observation.

The $\operatorname{\triangleleft_{lex}}$-maximal element of
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ is primitive by Lemma
2.6(1), so it should be $\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$. ∎

###### Proof of Theorem 2.5 (2).

Assume that the set

$\mathcal{D}=\\{D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2}):D\text{ is
not Erd\H{o}s-Gallai}\\}$

is not empty. Let $D^{*}$ be the $\operatorname{\triangleleft_{lex}}$-maximal
element of $\mathcal{D}$. If $D^{*}$ is not primitive then let
$\ell=\min\\{i:1\leq i\leq n:c_{2}<d_{i}<c_{1}\\}$ and $m=\max\\{i:1\leq i\leq
n:c_{2}<d_{i}<c_{1}\\}$. Then $\ell<m$ and so
$D^{*}+1^{+\ell}_{-m}\in\mathcal{D}$ and
$D^{*}\operatorname{\triangleleft_{lex}}D^{*}+1^{+\ell}_{-m}$. Contradiction,
and so the maximal element of $\mathcal{D}$ is primitive. So by Lemma 2.7,
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is in $\mathcal{D}$. ∎

######  Corollary 2.8.

A simple region $\mathbb{D}$ is fully graphic iff
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is graphic whenever
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\neq\emptyset$, and so
$\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}$.

###### Proof.

If $D\in\mathbb{D}$ is not graphic, then
$D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}$ for
some parameters $n,\Sigma,c_{1},c_{2}$, and
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is not Erdős-Gallai by Theorem
2.5(2). ∎

The following, easy to prove statement will simplify some arguments in Section
4.

######  Lemma 2.9.

Let $\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ be fully graphic, then
${\varphi}_{\rule{0.0pt}{4.52083pt}\\!{FG}}(n,c_{2},c_{1})$ holds, where

${\varphi}_{\rule{0.0pt}{4.52083pt}\\!{FG}}(n,c_{2},c_{1})\ \equiv\ \forall
k\in[1,n]\quad c_{1}\cdot k\leq k\cdot(k-1)+c_{2}\cdot(n-k)+1.$ (12)

Indeed, fix $k$. If $\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ is fully
graphic, then either $c_{1}k+(n-k)c_{2}$ or $c_{1}k+(n-k)c_{2}+1$ is even, so
either the sequence $(c_{1})_{k}(c_{2})_{n-k}$, or the sequence
$(c_{1})_{k}(c_{2}+1)(c_{2})_{n-k-1}$ is in
$\operatorname{\mathbb{D}}(n,c_{2},c_{1})$, and so it is graphic. We apply the
Erdős-Gallai theorem. In the first case the inequality holds with 1 surplus.
In the second case the displayed inequality holds.

##  3 The known $P$-stable, simple degree sequence regions are fully graphic

In this section we will show that some known $P$-stable degree sequence
regions are also fully graphic.

###  3.1 Sequences defined by minimum and maximum degrees

Our first result below clearly implies the statement (P1∗) from the
Introduction. In the proof we will use the machinery we developed in Section
2.

######  Theorem 3.1.

If $n>c_{1}\geq c_{2}$ are natural numbers such that

$(c_{1}-c_{2}+1)^{2}\leq 4c_{2}(n-c_{1}-1),$ (13)

then every sequence from $\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ has the
Erdős-Gallai property.

Before proving this result we should recall the following theorem. As the
authors remarked in the first lines of the proof of the “Theorem” in [19],
they actually proved the following statement.

######  Theorem 3.2 (Tripathi-Vijay [19]).

Assume that $D=(d_{1},d_{2},\dots,d_{n})$ is a non-increasing sequence of non-
negative integers and $n>d_{1}$. Then the following two statements are
equivalent:

  1. (1)

$D$ has the Erdős-Gallai property,

  2. (2)

$\eqref{eq:EG-prop}$ holds for $k\in\\{j:1\leq j\leq n\text{ and
}d_{j}>d_{j+1}\\}$.

###### Proof of of Theorem 3.1.

Assume on the contrary that
$D=(d_{1},\dots,d_{n})\in\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ is not
Erdős-Gallai. Write $\Sigma=\sum_{i=1}^{n}d_{i}$. By Theorem 2.5(2),
$E=\operatorname{LEG}(n,\Sigma,c_{1},c_{2})\in\operatorname{\mathbb{D}}(n,c_{1},c_{2})$
is not Erdős-Gallai, as well. $E$ has the form
$(c_{1})_{\alpha}a(c_{2})_{n-1-{\alpha}}$, where $c_{1}\geq a\geq c_{2}$.
Applying Theorem 3.2 for $E$ we obtain that (2.1) fails for $k={\alpha}$ or
for $k={\alpha}+1$.

In the first case:

$kc_{1}>k(k-1)+a+(n-k-1)c_{2}.$ (14)

Since $a\geq c_{2}$, we obtain

$kc_{1}>k(k-1)+c_{2}+(n-k-1)c_{2}.$ (15)

Rearranging, we obtain

$0>k^{2}-(c_{2}+c_{1}+1)k+nc_{2}.$ (16)

If we have two roots, then the discriminant of (16) should be positive:

$(c_{1}+c_{2}+1)^{2}-4nc_{4}>0$ (17)

Reordering (13) we obtain

$0\geq(c_{1}-c_{2}+1)^{2}-4c_{2}(n-c_{1}-1)=c_{1}^{2}+c_{2}^{2}+1-2c_{1}c_{2}+2c_{1}-2c_{2}-4nc_{2}-4c_{1}c_{2}-4c_{2}=\\\
c_{1}^{2}+c_{2}^{2}+2c_{1}c_{2}+2c_{1}+2c_{2}+1-e4nc_{2}=(c_{1}+c_{2}+1)^{2}-4c_{2}n,$

which contradicts (17)

In the second case:

$kc_{1}+a>k(k+1)+(n-k-1)c_{2}.$ (18)

Since $a\leq c_{1}$, we obtain

$(k+1)c_{1}>k(k+1)+(n-k-2)c_{2}.$ (19)

Let $\ell=k+1$. We obtain

$\ell c_{1}>\ell(\ell-1)+(n-\ell-1)c_{2}.$ (20)

Rearranging, we obtain

$0>\ell^{2}-(c_{2}+c_{1}+1)\ell+nc_{2}.$ (21)

But (21) is just (16), which leads contradiction again. ∎

###  3.2 Sequences defined by extremal degrees and degree sums

Concerning (P2) we could prove the following theorem which is stronger than
(P2∗), where the restriction concerning $c_{1}$ was $3\leq
c_{1}\leq\frac{1}{3}\sqrt{\Sigma}.$

######  Definition 3.3.

For any real $\epsilon>0$ define the property ${\varphi}_{\epsilon}$ as
follows:

${\varphi}_{\epsilon}(n,\Sigma,c_{1},c_{2})\quad\equiv\quad 2\leq c_{2}\
\text{ and }\ 3\leq c_{1}\leq\sqrt{(1-\epsilon)\Sigma}.$ (22)

######  Theorem 3.4.

For each positive $\epsilon$, the simple region
$\mathbb{D}[{\varphi}_{\epsilon}]$ is almost fully graphic.

###### Proof.

Assume that $D\in\mathbb{D}[{\varphi}_{\epsilon}]$ is not graphic. Then
$D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}$ for
some parameters $n,\Sigma,c_{1},c_{2}$ with
${\varphi}_{\epsilon}(n,\Sigma,c_{1},c_{2})$, and by Theorem 2.5(2),
$A=\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is not Erdős-Gallai.

Then sequence $A$ has the form $(c_{1})_{\alpha}a(c_{2})_{n-1-{\alpha}}$,
where $c_{1}\geq a\geq c_{2}$. Applying Theorem 3.2 for $A$ we obtain that
(2.1) fails for $k={\alpha}$ or for $k={\alpha}+1$.

In the first case, when $k={\alpha}$, we obtain

$kc_{1}>k(k-1)+a+(n-k-1)c_{2}.$ (23)

Since $a+(n-k-1)c_{2}=\Sigma-kc_{1}$, we have

$kc_{1}>k(k-1)+\Sigma-kc_{1}.$ (24)

Rearranging, we obtain

$0>k^{2}-(2c_{1}+1)k+\Sigma,$ (25)

and so, using $c_{1}\leq\sqrt{(1-\epsilon)\Sigma}$, we have

$0>k^{2}-(2\sqrt{(1-\epsilon)\Sigma}+1)k+\Sigma.$ (26)

Thus, the discriminant of (26) should be positive:

$\left(2\sqrt{(1-\epsilon)\Sigma}+1\right)^{2}-4\Sigma>0.$ (27)

In the second case, when $k={\alpha}+1$, we obtain

$kc_{1}+a>k(k+1)+(n-k-1)$ (28)

Using $\Sigma-(kc_{1}+a)=(n-k-1)c_{2}$, we obtain

$kc_{1}+a>k(k+1)+(\Sigma-(kc_{1}+a))$ (29)

Rearranging, we obtain

$0>k^{2}-(2c_{1}-1)k-2a+\Sigma\geq k^{2}-(2c_{1}+1)k+\Sigma.$ (30)

and so

$0>k^{2}-(2\sqrt{(1-\epsilon)\Sigma}+1)k+\Sigma.$ (31)

Thus, the discriminant of (31) should be positive:

$\left(2\sqrt{(1-\epsilon)\Sigma}+1\right)^{2}-4\Sigma>0.$ (32)

So far we established the following statement:

$\text{If
$D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}[{\varphi}_{\epsilon}]$
is not graphic, then
}\left(2\sqrt{(1-\epsilon)\Sigma}+1\right)^{2}-4\Sigma>0.$ (33)

But $\left(2\sqrt{(1-\epsilon)\Sigma}+1\right)^{2}-4\Sigma>0$ iff
$\Sigma<\frac{1}{4(1-\sqrt{1-\epsilon})^{2}}$. Since $\Sigma\geq 2n$, we
obtain

$\text{If
$D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}[{\varphi}_{\epsilon}]$
is not graphic, then $n<\frac{1}{8(1-\sqrt{1-\epsilon})^{2}}$}.$ (34)

So we proved there is a natural number $\Sigma_{\epsilon}$ such that every
element of $\mathbb{D}$ with length at least $\Sigma_{\epsilon}$ is graphic.
This completes the proof. ∎

######  Remark 3.5.

Using (34) one could estimate the value $\Sigma_{\epsilon}$ for concrete real
numbers. For example, in the case of (P2∗) we have $1-\epsilon=1/9$ and then
$\Sigma_{0}$ is 1, while in the case of $1-\epsilon=1/2$ the $\Sigma_{0}$ is
3.

Next we prove the statement of (P3∗).

######  Theorem 3.6.

The simple degree sequence region $\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$ is
fully graphic.

###### Proof.

Assume that $D\in\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$. We need to prove that
$D$ is Erdős-Gallai. Fix parameters $n,\Sigma,c_{1},c_{2}$ with
$D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})\subset\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$.
By Theorem 2.5(2), it is enough to prove that the sequence
$A=\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is Erdős-Gallai.

The sequence $A$ has the form $(c_{1})_{k}a(c_{2})_{n-1-k}$, where $c_{1}\geq
a\geq c_{2}$. Applying Theorem 3.2 for $A$ we obtain that $A$ is Erdős-Gallai
iff $(EG_{k})$ and $(EG_{k+1})$ holds, that is,

$kc_{1}\leq k(k-1)+(n-k)c_{2}+(\min\\{a,k\\}-c_{2}),$ ($EG_{k}$)

and

$kc_{1}+a\leq(k+1)k+(n-k-1)c_{2},$ ($EG_{k+1}$)

which can be rearranged as

$kc_{1}\leq k(k-1)+(n-k)c_{k}+(2k-c_{2}-a).$ ($EG^{*}_{k+1}$)

Consider the $\varphi^{*}_{J\\!M\\!S}$ inequality. Using the notation
$b=a-c_{2}$, we have

$\Sigma=kc_{1}+a+(n-k-1)c_{2}=nc_{2}+k(c_{1}-c_{2})+b.$

So, taking $x=\frac{b}{c_{1}-c_{2}}$, the LHS of $\varphi^{*}_{J\\!M\\!S}$ can
be written as follows:

$LHS=\big{[}k(c_{1}-c_{2})+b\big{]}\big{[}(n-k)(c_{1}-c_{2})-b\big{]}=\\\
(nk-k^{2})(c_{1}-c_{2})^{2}+(n-2k)b(c_{1}-c_{2})-b^{2}=\\\
(c_{1}-c_{2})^{2}\big{[}nk-k^{2}+(n-2k)x-x^{2}\big{]}.$ (35)

Now consider the RHS of $\varphi^{*}_{J\\!M\\!S}$:

$RHS=(c_{1}-c_{2})\Big{\\{}\big{[}(k(c_{1}-c_{2})+b\big{]}(n-c_{1}-1)+\big{[}(n-k)(c_{1}-c_{2})-b\big{]}c_{2}\Big{\\}}=\\\
(c_{1}-c_{2})^{2}\big{[}(k+x)(n-c_{1}-1)+(n-k-x)c_{2}\big{]}.$ (36)

Since $c_{1}-c_{2}>0$, putting together (35) and (36) we obtain

$nk-k^{2}+(n-2k)x-x^{2}\leq(k+x)(n-c_{1}-1)+(n-k-x)c_{2},\\\ $

which can be rearranged as:

$kc_{1}\leq k(k-1)+(n-k)c_{2}+x(2k+x-c_{1}-1-c_{2}).$ (37)

To derive ($EG_{k}$) we can assume that $c_{2}\leq k\leq c_{1}$ or $(EG_{k})$
holds as we proved it in Proposition 2.2. Moreover, it is enough to show that
the RHS of (37) is less than, or equal to RHS of ($EG_{k}$), that is,

$x(2k+x-c_{1}-1-c_{2})\leq\min\\{a,k\\}-c_{2}.$ (38)

Since $0\leq{x}<1$, we have

${x}\big{(}2k+{x}-(c_{1}+c_{2})-1\big{)}\leq
2k-(c_{1}+c_{2})=(k-c_{1})+(k-c_{2})\leq k-c_{2}.$ (39)

Since $x=\frac{b}{c_{1}-c_{2}}\leq 1$ and $k\leq c_{1}$, we have

$x(2k+x-c_{1}-1-c_{2})=b\frac{2k+x-c_{1}-1-c_{2}}{c_{1}-c_{2}}=\\\
b\frac{(c_{1}-c_{2})+(2k-2c_{1})+(x-1)}{c_{1}-c_{2}}\leq
b\frac{c_{1}-c_{2}}{c_{1}-c_{2}}=b.$ (40)

Since $\min(a,k)-c_{2}=\min(b,k-c_{2})$, putting together (40) and (39) we
obtain (38), which implies that $(EG_{k})$ holds.

To derive ($EG_{k+1}$) we can assume that $c_{2}\leq k+1\leq c_{1}$ by
Proposition 2.2, and it is enough to show that RHS of ($EG^{*}_{k+1}$) is
greater than, or equal to RHS of (37):

$x(2k+x-c_{1}-1-c_{2})\leq 2k-c_{2}-a.$ (41)

But $0\leq x\leq 1$, so

$x(2k+x-c_{1}-1-c_{2})=x(2k-c_{1}-c_{2}+(x-1))\leq(2k-c_{1}-c_{2})$ (42)

so (42) holds which implies $(EG^{*}_{k+1})$, and so $(EG_{k+1})$ as well.
This finishes the proof that the region $\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]$
is fully graphic. ∎

##  4 $P$-stable degree sequences

In this section we are considering fully graphic, simple degree sequence
regions, and want to prove that they are also $P$-stable regions. Along this
process we will strengthen the Jerrum, McKay and Sinclair’s theorem (P1).

###  4.1 Every fully graphic very simple degree sequence region is $P$-stable

In Section 1 the statement (P1) quoted the seminal result of Jerrum, McKay and
Sinclair from 1992:

######  Theorem 4.1 ([11, Theorem 8.1]).

The very simple region

$\mathbb{D}=\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]:=\bigcup\left\\{\operatorname{\mathbb{D}}(n,c_{1},c_{2}):(c_{1}-c_{2}+1)^{2}\leq
4c_{2}(n-c_{1}-1)\right\\}$ (43)

is $P$-stable.

Since in Theorem 3.1 we proved that the very simple region
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]$ is fully
graphic, therefore the next statement is a powerful strengthening of Theorem
4.1:

######  Theorem 4.2.

The largest fully graphic very simple region

$\mathbb{D}_{\max}\coloneqq\bigcup\\{\operatorname{\mathbb{D}}(n,c_{2},c_{1}):\text{
$\operatorname{\mathbb{D}}(n,c_{2},c_{1})$ is fully graphic}\\}$

is $P$-stable, and so the switch Markov chain is rapidly mixing on
$\mathbb{D}_{\max}$.

Careful study of the proof of [11, Theorem 8.1] reveals, that Jerrum, McKay
and Sinclair actually proved the following, slightly stronger result.

######  Theorem 4.3.

The very simple region
$\mathbb{D}[{\varphi}^{*}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}]$ is
P-stable, where the property
${\varphi}^{*}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}$ is defined as follows:

${\varphi}^{*}_{\rule{0.0pt}{4.52083pt}\\!{J\\!M\\!S}}(n,c_{1},c_{2})\ \equiv\
\forall k\in[1,n]\quad c_{1}\cdot k\leq k\cdot(k-1)+c_{2}\cdot(n-k).$ (44)

Unfortunately, Theorem 4.3 does not yield Theorem 4.2 because the assumption
that “every element of $\operatorname{\mathbb{D}}(n,c_{2},c_{1})$ is graphic”
does not imply (44). Fortunately, as we already proved (see Lemma 2.9), that
the following, slightly weaker inequality holds for a fully graphic
$\operatorname{\mathbb{D}}(n,c_{2},c_{1})$ :

${\varphi}_{\rule{0.0pt}{4.52083pt}\\!{FG}}(n,c_{2},c_{1})\ \equiv\ \forall
k\in[1,n]\quad c_{1}\cdot k\leq k\cdot(k-1)+c_{2}\cdot(n-k)+1.$

Using this observation, the following result, which is a direct strengthening
of Theorem 4.3, already yields Theorem 4.2.

######  Theorem 4.4.

If a graphic degree sequence ${D}=(d_{1},d_{2},\dots,d_{n})$ satisfies

$\forall k\in[1,n]\quad\sum_{i=1}^{k}d_{i}\leq k\cdot(k-1)+d_{n}\cdot(n-k)+1,$
(45)

then $\partial({D})\leq 3\cdot n^{9}$.

###### Proof.

Given a graph $G=\langle V,E\rangle$, an alternating trail of length $\ell$ is
a sequence of vertices $v_{0},\dots,v_{\ell}$ such that $\\{v_{i}v_{i+1}\\}$
is edge iff $i$ is zero or even, and the pairs
$\\{\\{v_{i},v_{i+1}\\}:i<\ell\\}$ are pairwise distinct. An alternating trail
is an alternating path if the vertices $x_{0},\dots,x_{n}$ are pairwise
different apart from the pair $\\{x_{0},x_{1}\\}$.

The proof of Theorem 4.4 is based on the following Lemma.

######  Lemma 4.5.

Let $D^{*}=D+1^{+p}_{+q}$ for some $1\leq p,q\leq n$, where $D$ satisfies
inequality $($45$)$. If $G$ is a graph with vertex set $V=\\{v_{1},\dots
v_{n}\\}$ and with degree sequence $D^{*}$, moreover
$\Gamma(v_{p})=\Gamma(v_{q})$, then there exists an alternating trail of odd
length 1, 3, 5 or 7 between $v_{p}$ and $v_{q}$, which contains one more edges
than non-edges.

###### Proof of Lemma 4.5.

Suppose for the contrary, that there is no such alternating trail. We will
describe the structure of $G.$ First, observe that either $v_{p}=v_{q}$ or the
edge $v_{p}v_{q}$ is missing (otherwise there is an alternating trail of
length $1$). Let

$S=\\{v_{p},v_{q}\\},\quad X=\Gamma(v_{p}),\quad Y=\\{y\in
V:|X\setminus\Gamma(y)|\geq 2\\},\quad Z=\Gamma(Y)\setminus X.$ (46)

Observe the following facts:

  1. (i)

The set $X$ is a clique (otherwise there is an alternating trail of length 3,
namely $v_{p}\to X\to X\to v_{q}$).

  2. (ii)

The set $Y$ is an independent set.

Indeed, if $\\{y_{0},y_{1}\\}\in{[Y]}^{2}\cap E$, then
$|X\setminus\Gamma(y_{i})|\geq 2$ for $i<2$ implies that there is
$\\{x_{0},x_{1}\\}\in{[X]}^{2}$ such that $\\{x_{i},y_{i}\\}\notin E$ for
$i<2$. Thus $v_{p},x_{0},y_{0},y_{1},x_{1},v_{q}$ is an alternating trail of
length 5.

  3. (iii)

The set $Z$ is a clique..

Indeed, if $\\{z_{0},z_{1}\\}\in{[X]}^{2}\setminus E$, then there are
$y_{0},y_{1}\in Y$ such that $\\{z_{i},y_{i}\\}\in E$ for $i<2$, but we can
not guarantee that $y_{0}\neq y_{1}$. Since $|X\setminus\Gamma(y_{i})|\geq 2$
for $i<2$, there is $\\{x_{0},x_{1}\\}\in{[X]}^{2}$ such that
$\\{x_{i},y_{i}\\}\notin E$ for $i<2$. Thus
$v_{p},x_{0},y_{0},z_{0},z_{1},y_{1},x_{1},v_{q}$ is an alternating trail of
length 7, but not necessarily a path.

  4. (iv)

The induced bipartite graph $G[X,Z]$ is complete, otherwise there exists an
alternating trail of length 5 between $v_{p}$ and $v_{q}$, namely
$v_{p}\rightarrow X\rightarrow Y\rightarrow Z\rightarrow X\rightarrow v_{q}$.

Indeed, if $x\in X$ and $z\in Z$ with $\\{x,z\\}\notin E$, then pick first
$y\in Y$ with $\\{y,z\\}\in E$. Since $|X\setminus\Gamma(y)|\geq 2$, we can
pick $x^{\prime}\in X$ such that $x^{\prime}\neq x$ and
$\\{x^{\prime},y\\}\notin E$. Then $x_{p},x,z,y,x^{\prime},v_{q}$ is an
alternating trail of length 5.

  5. (v)

The sets $\\{v_{p},v_{q}\\},X,Y,Z$ are pairwise disjoint.

Let

$K=X\cup Z\quad\text{ and }\quad R=V\setminus(K\cup Y\cup S).$

We have $|K|+|Y|+|R|+|S|=|V|=n$. Putting together (i), (iii) and (iv), we
obtain

  1. (vi)

$K$ is a clique.

Write $k=|K|$. We will estimate the sum of the degrees of the vertices in $K$.
To start with, write

$\sum_{i=1}^{k}d_{i}\geq\sum_{v\in K}\mathrm{deg}(v)=\\\ \sum_{v\in
K}|\Gamma(v)\cap K|+\sum_{v\in S}|\Gamma(v)\cap K|+\sum_{v\in R}|\Gamma(v)\cap
K|+\sum_{y\in Y}|\Gamma(y)\cap K|$ (47)

Since $K$ is a clique,

$\sum_{v\in K}|\Gamma(v)\cap K|=k\cdot(k-1).$ (48)

Since $\Gamma(v)=X\subset K$ for $v\in S$, we have

$\sum_{v\in S}|\Gamma(v)\cap K|=|S||X|.$ (49)

Since $|X\setminus\Gamma(v)|\leq 1$ for $v\in R$, we have

$\sum_{v\in R}|\Gamma(v)\cap K|\geq|R|(|X|-1).$ (50)

By the construction, $\Gamma(Y)\subset K$, so

$\sum_{y\in Y}|\Gamma(y)\cap K|\geq|Y|\cdot d_{n}.$ (51)

Putting together, we have

$\sum_{i=1}^{k}d_{i}\geq k\cdot(k-1)+|S|\cdot|X|+|R|\cdot(|X|-1)+|Y|\cdot
d_{n}.$ (52)

Since $|X|=\mathrm{deg}(v_{p})\geq d_{n}+(3-|S|)$, we obtain

$\sum_{i=1}^{k}d_{i}\geq
k\cdot(k-1)+|S|\cdot(d_{n}+3-|S|)+|R|(d_{n}+2-|S|)+|Y|d_{n}.$ (53)

Observe that $|R|+|Y|+|S|=n-k$. Clearly $|S|=1$ or $|S|=2$.

If $|S|=1$, then

$|S|\cdot(d_{n}+3-|S|)+|R|(d_{n}+2-|S|)+|Y|d_{n}=d_{n}+2+(|R|+|Y|)d_{n}+|R|=\\\
(|R|+|Y|+|S|)d_{n}+2+|R|\geq(n-k)d_{n}+2.$ (54)

If $|S|=2$, then

$|S|\cdot(d_{n}+3-|S|)+|R|(d_{n}+2-|S|)+|Y|d_{n}=2(d_{n}+1)+(|R|+|Y|)d_{n}=\\\
(|R|+|Y|+|S|)d_{n}+2=(n-k)d_{n}+2.$ (55)

So in both case, from (53) we obtain

$\sum_{i=1}^{k}d_{i}\geq k\cdot(k-1)+(n-k)d_{n}+2,$ (56)

which contradicts (45). So we proved Lemma 4.5. ∎

The proof of Theorem 4.4 from Lemma 4.5 is similar to the proof of [11,
Theorem 8.1] from [11, Lemma 1].

Assume that $G^{\prime}$ is a graph such that the degree sequence of
$G^{\prime}$ is $D^{\prime}=D+1^{+i}_{+j}$ for some $1\leq i<j\leq n$.

If $\Gamma_{G^{\prime}}(v_{i})=\Gamma_{G^{\prime}}(v_{j})$, then we can apply
Lemma 4.5 for $G=G^{\prime}$, $p=i$ and $q=j$ to obtain an alternating trail
$P$ of odd length 1, 3, 5 or 7 between $v_{i}$ and $v_{j}$, which contains one
more edges than non-edges. Flipping edges and non-edges along the trail $P$ we
obtain a graph $G^{\dagger}$ which is a realization of $D.$

If $\Gamma_{G^{\prime}}(v_{i})\neq\Gamma_{G^{\prime}}(v_{i})$, then there is
an alternating trail $Q$ of length $2$ between $v_{i}$ and $v_{j}$. Assume
that $Q=v_{i}v_{m}v_{j}$, where $v_{i}v_{m}$ is an edge, and $v_{m}v_{j}$ is a
non-edge. Flipping edges along trail $Q$ we obtain a graph $G^{*}$ with degree
sequence

$D^{*}=D^{\prime}+1^{+j}_{-i}=D+1^{+i}_{+j}+1^{-i}_{+j}=D+1^{+j}_{+j}.$

Now we can apply Lemma 4.5 for $G=G^{*}$ with $p=q=j$ to obtain an alternating
trail $P$ of odd length 1, 3, 5 or 7 from $v_{j}$ to $v_{j}$, which contains
one more edges than non-edges. Flipping edges and non-edges along the trail
$P$ we obtain a graph $G^{\dagger}$ which is a realization of $D.$

How much information should we use to obtain back $G^{\prime}$ from
$G^{\dagger}$? We need to know if we were in case
$\Gamma_{G^{\prime\prime}}(v_{i})=\Gamma_{G^{\prime\prime}}(v_{j})$ or in case
$\Gamma_{G^{\prime\prime}}(v_{i})\neq\Gamma_{G^{\prime\prime}}(v_{j})$.

If $\Gamma_{G^{\prime\prime}}(v_{i})=\Gamma_{G^{\prime\prime}}(v_{j})$, we
should know $P$. The trail $P$ contains at most 8 vertices, so this is at most
$n^{8}$ possibilities.

If $\Gamma_{G^{\prime\prime}}(v_{i})\neq\Gamma_{G^{\prime\prime}}(v_{j})$, we
should know $P$ and $Q$. Since the first and the last element of $P$ are the
same, we have at most $n^{7}$ possibilities for $P$. Knowing $P$ we can
compute $G^{*}$, and we also know $v_{i}$ or $v_{j}$. We should know $Q$. We
know one vertex ($v_{i}$ or $j$) from $Q$. So knowing P we have $n^{2}$
possibilities for $Q$. Knowing $Q$ we can compute $G^{\prime\prime}$. We
should know which endpoint of $Q$ is $v_{i}$ and which is $v_{j}$. In this
case we have at most $2\cdot n^{2}\cdot n^{7}=2\cdot n^{9}$ possibilities.

Putting together, for a given $G^{*}$ we have at most $n^{8}+2\cdot n^{9}\leq
3\cdot n^{9}$ possibilities for $G^{\dagger}$. ∎

The next theorem gives us a method to prove that a simple region
$\mathbb{D}[{\varphi}]$ is P-stable. Namely, it is enough to prove that
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ satisfies (45) from Theorem 4.4
whenever ${\varphi}(n,\Sigma,c_{1},c_{2})$ holds.

######  Theorem 4.6.

If $n>c_{1}\geq c_{2}$ and $nc_{1}\geq\Sigma\geq nc_{2}$ are natural numbers
then the following are equivalent:

  1. (1)

$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ satisfies (45) from Theorem 4.4,

  2. (2)

every $D\in\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$ satisfies the (45)
from Theorem 4.4.

###### Proof.

To show that (1) implies (2), let $D=(d_{1},\dots,d_{n})$ be an arbitrary
element of $\operatorname{\mathbb{D}}(n,\Sigma,c_{1},c_{2})$, and fix $1\leq
k\leq n$. Write $LEG(n,\Sigma,c_{1},c_{2})=(e_{1},\dots,e_{n})$. Then,
$\sum_{i=1}^{k}d_{i}\leq\sum_{i=1}^{k}e_{i}$, and $\sum_{i=1}^{k}e_{i}\leq
k(k-1)+(n-k)e_{n}+1$ because $\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$
satisfies (45). Putting together these two inequalities we obtain

$\sum_{i=1}^{k}d_{i}\leq k(k-1)+(n-k)e_{n}+1=k(k-1)+(n-k)c_{2}\leq
k(k-1)+(n-k)d_{n}+1,$

which implies that (45) holds for $D$ and $k$. ∎

By $(P2)$, the simple region
$\mathbb{D}[{\varphi}_{\rule{0.0pt}{4.52083pt}\\!{GS}}]=\mathbb{D}[{\varepsilon}_{2/3}]$
is P-stable. We also proved that $\mathbb{D}[{\varphi}_{\varepsilon}]$ is
fully graphic for ${\varepsilon}>0$. The next question is very natural.

######  Problem 4.7.

Is the simple region $\mathbb{D}[{\varphi_{\epsilon}}]$ P-stable for
${\varepsilon}>0$?

###  4.2 Construction of $P$-stable families with special properties

We demonstrate the existence of a fully graphic simple region, whose
P-stability can be derived from Theorem 4.4, whereas application of [11,
Theorem 8.3] does not yield its P-stability.

######  Theorem 4.8.

The simple region

$\mathbb{D}_{0}=\bigcup\\{\operatorname{\mathbb{D}}(2m,4m,m,1):m\geq 4\\}$
(57)

is fully graphic and P-stable, but
$\mathbb{D}_{0}\cap\mathbb{D}[\varphi^{*}_{J\\!M\\!S}]=\emptyset$.

###### Proof.

First, observe that

$D_{m}\coloneqq(m,m,3)^{\frown}(1)_{2m-3}=\operatorname{LEG}(2m,4m,m,1).$ (58)

######  Lemma 4.9.

For $m\geq 4$, $D_{m}$ does not satisfy the $\varphi^{*}_{J\\!M\\!S}$
inequality.

###### Proof.

Indeed, $n=2m$, $c_{1}=m$, $c_{2}=1$, $\Sigma=4m$, so

$LHS_{\varphi^{*}_{J\\!M\\!S}}-RHS_{\varphi^{*}_{J\\!M\\!S}}=\\\ (\Sigma-
c_{2}n)(c_{1}n-\Sigma)-(c_{1}-c_{2})[(\Sigma-
c_{2}n)(n-c_{1}-1)+(c_{1}n-\Sigma)c_{2}]=\\\
4(m^{2}-2m)m-[2((m-1)m+m^{2}-2m)(m-1)]=2m^{2}-6m.$

which is positive for $m\geq 4$, so we proved the Lemma. ∎

######  Lemma 4.10.

$D_{m}$ is graphic.

###### Proof.

By the Tripathi-Vijay Theorem 3.2, we should check only $EG_{2}$ and $EG_{3}$
for $D_{m}$. But

$\sum_{i=1}^{2}d_{i}=2m<2+(2+(2m-3)\cdot
1)=2(1-2)+\sum_{i=3}^{2m}\min(d_{i},2),$ ($EG_{2}$)

and

$\sum_{i=1}^{3}d_{i}=2m+3=6+(2m-3)\cdot
1=3(3-1)+\sum_{i=4}^{2m}\min(d_{i},3).$ ($EG_{3}$)

∎

######  Lemma 4.11.

$D_{m}$ satisfies (45) from Theorem 4.4.

###### Proof.

If $k=1,2,3$, (45) is the following:

$\displaystyle d_{1}=m\leq 1(1-0)+(2m-1)1+1$ ($k=1$) $\displaystyle
d_{1}+d_{2}=2m<2(2-1)+(2m-2)1+1,$ ($k=2$) $\displaystyle
d_{1}+d_{2}+d_{3}=2m+3\leq 3(3-1)+(2m-3)1+1,$ ($k=3$)

If $k\geq 3$, then $EG_{k}$ implies $EG_{k+1}$, because , the LHS is increased
by 1, and the RHS is increased by $2k-1$. ∎

The lemmas together prove the theorem. ∎

##  5 Large fully graphic regions in very simple P-stable regions

In the first two subsections we review the necessary facts about split graphs
and Tyshkevich product.

### Split graphs.

A $G=(V,E)$ graph is a _split graph_ if its vertices can be partitioned into a
clique and an independent set. Split graphs were introduced by Földes and
Hammer ([7]).

Split graphs are recognizable from their degree sequences:

######  Theorem 5.1 (Hammer and Simeone, 1981 [10], Tyshkevich, Melnikov and
Kotov [17]).

Assume that $G$ is a graph with degree sequence $D=(d_{1},\dots,d_{n})$, where
$d_{1}\geq d_{2}\geq\dots\geq d_{n}$. Let $m$ be the largest value of $\,i$,
such that $d_{i}\geq i-1.$ Then $G$ is a split graph if and only if

$\sum_{i=1}^{m}d_{i}=m(m-1)+\sum_{i=m+1}^{n}d_{i}.$

######  Remark 5.2.

Consequently, if one realization of a degree sequence $D$ is a split graph,
then all realizations of $D$ are split graphs as well. Such a degree sequence
is referred as _split degree sequence_.

We will write $G=((U,W),E)$ to mean that $G$ is a split graph with vertex set
$U\cup W$, $U$ is a clique and $W$ is an independent set. Let us remark that
$U$ and $W$ are not necessarily unique.

######  Theorem 5.3.

If $\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ is not fully graphic, then
$\operatorname{\mathbb{D}}(n,c_{1},c_{2})$ contains a split degree sequence.

###### Proof.

Fix a non-graphic $D\in\operatorname{\mathbb{D}}(n,c_{1},c_{2})$. Write
$\Sigma=\sum D$. By Corollary 2.8 the sequence
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})$ is not graphic.

######  Lemma 5.4.

There is $c_{2}\leq\ell\leq c_{1}$ such that

$\ell c_{1}>\ell(\ell-1)+(n-\ell)c_{2}.$ (60)

###### Proof of the Lemma.

Write
$\operatorname{LEG}(n,\Sigma,c_{1},c_{2})=(d_{1},\dots,d_{n})=((c_{1})_{k},a,(c_{2})_{n-2})$,
where $c_{2}\leq a\leq c_{1}$.

By the Tripathi-Vijay Theorem 3.2, either EGk or EGk+1 fails. By Proposition
2.2 property (EGℓ) holds for each $\ell\leq c_{2}$ or $\ell>c_{1}$. So we can
assume that $c_{2}\leq k<c_{1}$.

Case 1: If (EGk) fails, then

$\sum_{i=1}^{k}d_{i}>k(k-1)+\sum_{i=k+1}^{n}\min(d_{i},k),$ (61)

and so

$kc_{1}>k(k-1)+\min(a,k)+(n-k-1)c_{2},$ (62)

and so

$kc_{1}>k(k-1)+(n-k)c_{2}.$ (63)

Case 2: If (EGk+1) fails, then

$\sum_{i=1}^{k+1}d_{i}>(k+1)k+\sum_{i=k+2}^{n}\min(d_{i},k).$ (64)

and so

$kc_{1}+a>(k+1)k+(n-k-2)c_{2},$ (65)

and so

$(k+1)c_{1}>(k+1)k+(n-k-1)c_{2}.$ (66)

So either $\ell=k$ or $\ell=k+1$ has the following property:
$c_{2}\leq\ell\leq c_{1}$ and

$\ell c_{1}>\ell(\ell-1)+(n-\ell)c_{2}.$ (67)

So we proved the Lemma. ∎

Let

$\sigma=(n-\ell)c_{2},\qquad
c=\lfloor\sigma/\ell\rfloor,\qquad{\alpha}=\sigma-\ell c.$ (68)

Then

$(n-\ell)c_{2}={\sigma}={\alpha}(c+1)+(\ell-{\alpha})c.$

Consider the following degree sequence

$D=(\ell+c)_{{\alpha}}(\ell+c-1)_{\ell-{\alpha}}(c_{2})_{n-\ell}$ (69)

######  Lemma 5.5.

The previous degree sequence is
$D\in\operatorname{\mathbb{D}}(n,c_{1},c_{2})$, and it is a graphic split
sequence.

###### Proof.

First observe that $D$ is graphic. Really, it has a realization $G=\langle
V,E\rangle$ on the vertex set $V=\\{v_{j}:j<\ell\\}\cup\\{w_{k}:k<n-\ell\\}$
with

$E=\big{\\{}(v_{i},v_{j}):i<j<\ell\big{\\}}\cup\big{\\{}(v_{i\bmod\ell},w_{i\bmod{(n-\ell)}}):i<\sigma\big{\\}}.$
(70)

Next observe that $\ell$ is the largest $j$ such that $d_{j}\geq j-1$.
Moreover,

$\sum_{i=1}^{\ell}d_{i}=(\ell+c){{\alpha}}+(\ell+c-1)({\ell-{\alpha}})=\sigma+\ell(\ell-1)\\\
=\ell(\ell-1)+c_{2}({n-\ell})=\ell(\ell-1)+\sum_{i=\ell+1}^{n}d_{i}.$

Thus the degree sequence $D$ is a split degree sequence. ∎

This completes the proof of the Theorem 5.3. ∎

### Tyshkevich product

######  Definition 5.6 (Tyshkevich [18]).

Let $G=(\langle U,W\rangle;E)$ be a split graph and $H=(V,F)$ be an arbitrary
graph. We define the composition graph $K=G\circ H$ as follows: $K$ consists
of a copy of $G$, and a copy of $H$ and of all the possible new edges $(u,v)$
where $u\in U,v\in V.$ More formally,

$V(K)=U\cup W\cup V\text{ and }E(K)=E\cup F\cup\\{(u,v):u\in U,v\in V\\}.$

Observe that the first operand in this operation is always a split graph.

Barrus [6, Theorem 3.5] proved the following (see also [1, Theorem 6]):

######  Theorem 5.7.

Assume that $G=(\langle U,W\rangle;E)$ is a split graph and $H=(V,F)$ is an
arbitrary graph. Let $K=G\circ H$. Then

$|\mathcal{G}(\mathbf{d}(K))|=|\mathcal{G}(\mathbf{d}(G))|\cdot|\mathcal{G}(\mathbf{d}(H))|.$
(71)

### How to obtain ,,not P-stable” from ,,not fully graphic”?

######  Theorem 5.8.

Assume that

$\mathbb{D}=\bigcup_{k\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n_{k},c_{k,1},c_{k,2})\text{
and
}\mathbb{D}^{\prime}=\bigcup_{k\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n^{\prime}_{k},c^{\prime}_{k,1},c^{\prime}_{k,2})$

are infinite families of finite sequences. If $\mathbb{D}$ is not almost fully
graphic, then $\mathbb{D}^{\prime}$ is not P-stable provided:

  1. (1)

$\lim_{k\to\infty}(n^{\prime}_{k}-n_{k})/\ln(n^{\prime}_{k})=+\infty$,

  2. (2)

$c^{\prime}_{k,2}\leq c_{k,2}$,

  3. (3)

$c^{\prime}_{k,1}\geq c_{k,1}+(n^{\prime}_{k}-n_{k})$.

###### Proof.

We will use a construction, which is similar to the one Jerrum, McKay and
Sinclair derived in [11, Lemma 8.1], and based on the result [4, Corollary
6.2].

######  Lemma 5.9.

For each natural number $m\geq 1$ the following sequence

$\mathbf{h}_{m}=(2m-1,2m-2,\dots,m+1,m,m,m-1,\dots,2,1),$ (72)

has exactly one realization $H_{m}=(V,E)$ on the vertex set
$V=\\{v_{1},\dots,v_{2m}\\}$, namely

$E=\\{(i,j):m+1\leq i<j\leq 2m\\}\cup\\{(i,j):1\leq i\leq m<j\leq 2m,i+j\leq
2m+1\\}.$

However the sequence

$\mathbf{h}^{\prime}_{m}=\mathbf{h}_{m}+1^{+2m}_{+m}=({2m-1},2m-2,\dots,m+1,\mathbf{m+1},m-1,m-2,\dots,2,\mathbf{2})$
(73)

has at least $\Theta(e^{{{\delta}m}})$ realizations for some ${\delta}>0$.

$v_{2m}$$v_{2m-1}$$v_{m+2}$$v_{m+1}$$v_{m}$$v_{m-1}$$v_{2}$$v_{1}$…… Figure 1:
The unique realization of $\mathbf{h}_{m}$.

###### Proof.

It is easy to see that the degree sequence $\mathbf{h}_{m}$ has exactly one
realization (see, for example, [11, Lemma 8.1]).

The calculation concerning the number of realizations of
$\mathbf{h}^{\prime}_{m}$ follows from [4, Corollary 6.2], which claims that
the bipartite degree sequence $((m,m-1,\dots,2,2),((m,m-1,\dots,2,2))$ has

$\Theta\left({\left(\frac{3+\sqrt{5}}{2}\right)}^{{m}}\right)$

realizations. ∎

Let
$I=\\{k\in\mathbb{N}:\text{$\operatorname{\mathbb{D}}(n_{k},c_{k,1},c_{k,2})$
contains a non-Erd\H{o}s-Gallai\ sequence}\\}$. By the assumption of Theorem,
the set $I$ is infinite. Replacing $\mathbb{D}$ with
$\bigcup\\{\operatorname{\mathbb{D}}(n_{k},c_{k,1},c_{k,2}):{n\in I}\\}$, we
can assume that every $\operatorname{\mathbb{D}}(n_{k},c_{k,1},c_{k,2})$
contains a non-Erdős-Gallai sequence. Therefore, by Theorem 5.3, every
$\operatorname{\mathbb{D}}(n_{k},c_{k,1},c_{k,2})$ contains a split degree
sequence $D_{k}$. Let $G_{k}$ be the unique realization of $D_{k}$.
Furthermore, for each $k$ let
$H_{k}^{*}=H_{\rule{0.0pt}{4.52083pt}{n_{k}^{\prime}-n_{k}}}$ be the unique
realization of the graphic degree sequence
$\mathbf{h}_{\rule{0.0pt}{4.52083pt}{n_{k}^{\prime}-n_{k}}}$.

Let $\mathbf{e}_{k}$ be the degree sequence of the Tyshkevich product
$G_{k}\circ H_{k}$. Clearly
$\mathbf{e}_{k}\in\operatorname{\mathbb{D}}(m_{k}^{\prime},c^{\prime}_{k,2},c^{\prime}_{k1})$
by the construction. Then, by Theorem 5.7, $\mathbf{e}_{k}$ has exactly one
realization because both $\mathbf{d}_{k}$ and
$\mathbf{h}_{\rule{0.0pt}{4.52083pt}{n_{k}^{\prime}-n_{k}}}$ have exactly one
realization.

However, for some $i$ and $j$, the sequence $\mathbf{e}_{k}+1^{+i}_{+j}$ has
at least

$C\cdot e^{{{\delta}(n^{\prime}_{k}-n_{k})}}$

realizations by Theorem 5.7 and by the second part of the Lemma 5.9.

Let $p$ be an arbitrary polynomial. Then

$\lim_{k\to\infty}\ln\Big{(}\frac{C\cdot
e^{{{\delta}(n^{\prime}_{k}-n_{k})}}}{p(n^{\prime}_{k})}\Big{)}\geq\lim_{k\to\infty}\Big{(}C^{\prime}\cdot({{n^{\prime}_{k}-n_{k}}})-C^{\prime\prime}\cdot\ln(n^{\prime}_{k})\Big{)}=\infty,$

by assumption (1) of this Theorem. Thus, the ration of the number of
realizations of $\mathbf{e}_{k}$ and $p(k)$ tends to infinity. So
$\mathbb{D}^{\prime}$ is not P-stable. ∎

######  Theorem 5.10.

Assume that $f,g,h\in\mathbb{N}^{\mathbb{N}}$ are increasing functions . If
the cone region $\mathbb{D}(f,g)$ is P-stable, then $\mathbb{D}(f+h,g-h)$ is
almost fully graphic provided

  1. (1)

$f(n+k)\leq f(n)+k$ for each $n,k\in{\mathbb{N}}$,

  2. (2)

$lim_{n\to\infty}h(n)/\ln(n)=\infty$.

###### Proof of Theorem 5.10.

Assume on the contrary that $\mathbb{D}(f+h,g-h)$ is not almost fully graphic.
Let

  1. (i)

$n_{k}=k$, $c_{k,1}=g(n_{k})-h(n_{k})$, $c_{k,2}=f(n_{k})+h(n_{k})$,

  2. (ii)

$n_{k}^{\prime}=n_{k}+h(n_{k})$, $c^{\prime}_{k,1}=g(n^{\prime}_{k})$
$c^{\prime}_{k,2}=f(n^{\prime}_{k})$.

The assumption Theorem 5.10 (2) implies that 5.8(1) holds. The assumption
Theorem 5.10 (1) implies that 5.8(2) holds. Finally Theorem 5.10 (1) also
implies that $g(n_{k,1})\geq c_{k,1}+h(n_{k})$, and $g(n^{\prime}_{k,1})\geq
g(n_{k,1})$ because $g$ is monotone. So 5.8(3) holds.

Hence, we can apply Theorem 5.8 to obtain that $\mathbb{D}(f,g)$ is not
P-stable. ∎

######  Corollary 5.11.

Assume that
$0\leq{\varepsilon}_{2}<{\varepsilon}^{\prime}_{2}<{\varepsilon}^{\prime}_{1}<{\varepsilon}_{1}\leq
1$. If the very simple region
$\mathbb{D}\coloneqq\bigcup_{n\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n,\lfloor{\varepsilon}_{1}\cdot
n\rfloor,\lceil{\varepsilon}_{2}\cdot n\rceil)$ is P-stable, then the region
$\mathbb{D}^{\prime}=\bigcup_{n\in{\mathbb{N}}}\operatorname{\mathbb{D}}(n,\lfloor{\varepsilon}^{\prime}_{1}\cdot
n\rfloor,\lceil{\varepsilon}^{\prime}_{2}\cdot n\rceil)$ is almost fully
graphic.

##  6 A common bound of the growing rate in P-stable regions

In the literature, various P-stable families of degree sequences are
described. However, the empirical evidence is that the polynomial
$p_{0}(n)=n^{10}$ has the following property: if $\mathbb{D}$ is P-stable,
then $\partial(D)\leq p_{0}(|D|)$ for all but finitely many $D\in\mathbb{D}$.
This observation is notable and leads to the following bold conjecture.

######  Conjecture 6.1.

There is a polynomial $p^{*}(n)$ such that for each P-stable family
$\mathbb{D}$ of degree sequences (or, just for each P-stable simple region
$\mathbb{D}$)

$\partial(D)\leq p^{*}(|D|)$

for all but finitely many graphic $D\in\mathbb{D}$.

## References

  * [1] M.D. Barrus: On realization graphs of degree sequences. Discrete Math. 339 2146–2152.
  * [2] M. Dyer - C. Greenhill - P. Kleer - J. Ross - L. Stougie: Sampling hypergraphs with given degrees, Discrete Mathematics 344(11) (2021), #112566, DOI:10.1016/j.disc.2021.112566
  * [3] P. Erdős - T. Gallai: Graphs with prescribed degree of vertices (in Hungarian), Mat. Lapok 11 (1960), 264–274.
  * [4] P.L. Erdős - E. Győri - T.R. Mezei - I. Miklós - D. Soltész: Half-graphs, other non-stable degree sequences, and the switch Markov chain, Electronic Journal of Combinatorics 28(3) (2021), #P3.7, pp. 32. DOI:10.37236/9652
  * [5] P.L. Erdős - C. Greenhill - T.R. Mezei - I. Miklós - D. Soltész - L. Soukup: The mixing time of switch Markov chains: a unified approach, European J. Combinatorics 99 (2022), 1–46. # 103421. DOI:10.1016/j.ejc.2021.103421
  * [6] P. L. Erdős - I. Miklós - Z. Toroczkai: New classes of degree sequences with fast mixing swap Markov chain sampling. Combin. Probab. Comput. 27 (2018), no. 2, 186–207.
  * [7] S. Földes - P.L. Hammer: Split graphs, in Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Math. 19 (1977), 311–315.
  * [8] Gao, P. – Greenhill, C.: Mixing time of the switch Markov chain and stable degree sequences, Discrete Applied Mathematics 291 (2021), 143–162. DOI:10.1016/j.dam.2020.12.004
  * [9] Greenhill, C. – Sfragara, M.: The switch Markov chain for sampling irregular graphs, Theoretical Comp. Sci 719 (2018), 1–20. DOI:10.1016/j.tcs.2017.11.010
  * [10] P.L. Hammer - B. Simeone: The splittance of a graph, Combinatorica 1 (3) (1981), 275–284. DOI:10.1007/BF02579333
  * [11] M.R. Jerrum - B.D. McKay - A. Sinclair: When is a Graphical Sequence Stable? Chapter 8 in Random Graphs: Volume 2 Eds.: A. Frieze and T. Luczak, Wiley, (1992), pp. 304. ISBN: 978-0-471-57292-3
  * [12] M.R. Jerrum - A. Sinclair: Approximating the Permanent, SIAM J. Comput., 18 (6) (1989), 1149–1178. DOI:10.1137/0218077
  * [13] M.R. Jerrum - A. Sinclair: Fast uniform generation of regular graphs, Theoret. Computer Sci. 73 (1990), 91–100. DOI:10.1016/0304-3975(90)90164-D
  * [14] Kannan, R. – Tetali, P. – Vempala, S.: Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Extended abstract, in Proc. SODA ’97 (1997), 193–200. ISBN:0-89871-390-0
  * [15] J. Salas - V. Torra: Improving the characterization of P-stability for applications in network privacy, Discrete Applied Mathematics 206 (2016,) 109–114. DOI:10.1016/j.dam.2016.01.025
  * [16] V. Torra - T. Shafie - J. Salas: Data Protection for Online Social Networks and $P$-Stability for Graphs, IEEE Transactions On Emerging Topics In Computing (2015), 374–381. DOI:10.1109/TETC.2015.2433923
  * [17] R. Tyshkevich - O. Melnikov - V. Kotov: On graphs and degree sequences, (in Russian) Kibernetika 6 (1981), 5–8.
  * [18] R. Tyshkevich: Decomposition of graphical sequences and unigraphs, Discrete Math. 220 (1-3) (2000), 201–238. DOI:10.1016/S0012-365X(99)00381-7
  * [19] A. Tripathi - S. Vijay: A note on a theorem of Erdős and Gallai, Discrete Math. 265 (2003), 417-–420. DOI:10.1016/S0012-365X(02)00886-5

## Appendix: the different definitions of P-stability are really equivalent

Given a degree sequence $D$ of length $n$, define the following families of
degree sequences:

$\displaystyle\mathcal{D}^{-+}$ $\displaystyle=\big{\\{}D+1^{-i}_{+j}:1\leq
i\neq j\leq n\big{\\}},\vskip 6.0pt plus 2.0pt minus 2.0pt$
$\displaystyle\mathcal{D}^{++}$ $\displaystyle=\big{\\{}D+1^{+i}_{+j}:1\leq
i\neq j\leq n\big{\\}},\vskip 6.0pt plus 2.0pt minus 2.0pt$
$\displaystyle\mathcal{D}^{+2}$ $\displaystyle=\big{\\{}D+1^{+i}_{+i}:1\leq
i\leq n\big{\\}}.$

The families $\mathcal{D}^{--}$ and $\mathcal{D}^{-2}$ are defined
analogously.

In 1989 Jerrum and Sinclair introduced the so-called _Jerrum-Sinclair Markov
Chain_ (JSMC) in their seminal paper [12] on the approximation of the zero-one
permanents. Later they used the same Markov chain to sample certain graph
realization classes on labelled vertices in [13]. They introduced there the
notion of P-stability: a family $\mathcal{D}$ of degree sequences is P-stable
iff there is a polynomial $p(n)$ such that for each graphic sequence
$D\in\mathcal{D}$ with length $n$ we have

$|\mathbb{G}(\mathcal{D}^{--})\cup\mathbb{G}(\mathcal{D}^{-2})|\leq
p(n)\cdot|\mathcal{G}(D)|.$

In 1992 Jerrum, McKay and Sinclair gave more results about P-stable degree
sequences ([11, Subsection 8.2]). However they used there a different
definition. They say that a family $\mathcal{D}$ of degree sequences is
P-stable  iff there is a polynomial $p_{1}(n)$ such that for each graphic
sequence $D\in\mathcal{D}$ with length $n$ we have

$|\mathbb{G}(\mathcal{D}^{-+})|\leq p_{1}(n)\cdot|\mathcal{G}(D)|.$

The authors made the remark (without proof) that, while the two definitions
formally are different, they are equivalent.

There is another Markov chain based approach to sample graph realizations for
at least three decades, the chain is called _switch Markov Chain_. In 2022,
the rapid mixing of the switch Markov chain was proven on P-stable degree
sequences, encompassing all simple, bipartite, and directed degree sequences
([5]), providing the currently available strongest result. However, that paper
presented a third definition for P-stability [5, Definition 1.2]. They say
that a family $\mathcal{D}$ of degree sequences is P-stable  iff there is a
polynomial $p_{2}(n)$ such that for each graphic sequence $D\in\mathcal{D}$
with length $n$ we have

$|\mathbb{G}(\mathcal{D}^{++})|\leq p_{2}(n)\cdot|\mathcal{G}(D)|.$

The paper states (again, without proof) that this definition is equivalent to
the former ones.

The following theorem yields immediately that the three definitions of
P-stability are indeed equivalent.

######  Theorem 6.2.

Assume that $D=(d_{1},\dots,d_{n})$ is a graphic degree sequence.

  1. (a)

$\max\big{(}|\mathbb{G}(\mathcal{D}^{++})|,|\mathbb{G}(\mathcal{D}^{--})|\big{)}\leq
n^{2}\cdot\big{(}|\mathbb{G}(\mathcal{D}^{+-})|+|\mathcal{G}(D)|\big{)},$

  2. (b)

$\max\big{(}|\mathbb{G}(\mathcal{D}^{+2})|,|\mathbb{G}(\mathcal{D}^{-2})|\big{)}\leq
n^{2}\cdot|\mathbb{G}(\mathcal{D}^{+-})|$,

  3. (c)

$|\mathbb{G}(\mathcal{D}^{+-})|\leq(n^{4}+n^{2})\cdot\min\big{(}|\mathbb{G}(\mathcal{D}^{++})|,|\mathbb{G}(\mathcal{D}^{--})|\big{)}$.

######  Remark.

The proofs for (a) and (b) are straightforward. However, proving (c) presents
a greater challenge.

###### Proof.

We assume that the vertex set of the realizations is
$\\{v_{1},\dots,v_{n}\\}$.

(a) Assume that
$G\in\mathcal{G}(D+1^{+i}_{+j})\subset\mathbb{G}(\mathcal{D}^{++})$ for some
$1\leq i\neq j\leq n$. We will define a graph
$G^{\prime}\in\mathbb{G}(\mathcal{D}^{+-})\cup\mathcal{G}(D)$ such that the
symmetric difference of $E(G)$ and $E(G^{\prime})$ is one edge.

If $(v_{i},v_{j})\in E(G)$, then let $G^{\prime}=G-(v_{i},v_{j})$. Then
$\mathbf{d}(G^{\prime})=\mathbf{d}(G)+1^{-i}_{-j}=D$, so $G^{\prime}$
satisfies the requirements.

Assume that $(v_{i},v_{j})\notin E(G)$. Since
$\mathrm{deg}_{G}(v_{i})=d_{i}+1\geq 1$, there is $k$ such that $v_{i}v_{k}$
is an edge in $G$. Since $(v_{i},v_{j})$ is a non-edge, $k\neq j$. Let
$G^{\prime}=G-v_{i}v_{k}$. Then
$\mathbf{d}(G^{\prime})=\mathbf{d}(G)+1^{-i}_{-k}=D+1^{+i}_{+j}+1^{-i}_{-k}=D^{+j}_{-k}$,
so $G^{\prime}$ satisfies the requirements.

From $G$ you can get back $G^{\prime}$ provided you know the symmetric
difference of $E(G)$ and $E(G^{\prime})$, which is just one pair of vertices.
Since there are less than $n^{2}$ many pairs, edges in $G$, for any
$H\in\mathbb{G}(\mathcal{D}^{+-})\cup\mathcal{G}(D)$ there are less than
$n^{2}$ many $G\in\mathbb{G}(\mathcal{D}^{++})$ such that $G^{\prime}=H$. So
we proved $|\mathbb{G}(\mathcal{D}^{++})|\leq
n^{2}\cdot\big{(}|\mathbb{G}(\mathcal{D}^{+-})|+|\mathcal{G}(D)|\big{)}.$

The inequality $|\mathbb{G}(\mathcal{D}^{--})|\big{)}\leq
n^{2}\cdot\big{(}|\mathbb{G}(\mathcal{D}^{+-})|+|\mathcal{G}(D)|\big{)}$ can
be proved analogously

(b) Assume that
$G\in\mathcal{G}(D+1^{+i}_{+i})\subset\mathbb{G}(\mathcal{D}^{+2})$ for some
$1\leq i\leq n$.

We will define a graph $G^{\prime}\in\mathbb{G}(\mathcal{D}^{+-})$ such that
the symmetric difference of $E(G)$ and $E(G^{\prime})$ is one edge. Since
$\mathrm{deg}_{G}(v_{i})=d_{i}+2>0$, there is $j$ such that $(v_{i},v_{j})\in
E(G)$. Then $G^{\prime}=G-(v_{i},v_{j})$ meets the requirements because
$\mathbf{d}(G^{\prime})=\mathbf{d}(G)+1^{-i}_{-j}=D+1^{+i}_{+i}+1^{-i}_{-j}=D+1^{+i}_{-j}$.
Since there are less than $n^{2}$ edges in $G$, for any
$H\in\mathbb{G}(\mathcal{D}^{+-})$ there are less than $n^{2}$ many
$G\in\mathbb{G}(\mathcal{D}^{+2})$ such that $G^{\prime}=H$. So we proved
$|\mathbb{G}(\mathcal{D}^{+2})|\leq n^{2}\cdot|\mathbb{G}(\mathcal{D}^{+-})|$.

The inequality $|\mathbb{G}(\mathcal{D}^{-2})|\leq
n^{2}\cdot|\mathbb{G}(\mathcal{D}^{+-})|$ can be proved analogously.

(c) For each $G\in\mathbb{G}(\mathcal{D}^{+-})$ we will find a
$G^{\prime}\in\mathbb{G}(\mathcal{D}^{++})$ such that the symmetric difference
of $E(G)$ and $E(G^{\prime})$ is either an edge, or a path of length 3. Fix
$i,j$ such that $G\in\mathcal{G}(D+1^{+j}_{-i})$. If there is $k\neq i,j$ such
that $v_{i}v_{k}$ is not an edge, then let

$G^{\prime}=G+(v_{i},v_{j}).$

Then $\mathbf{d}(G^{\prime})=1^{+j}_{+k}$, so $G^{\prime}$ satisfies the
requirements.

So we can assume that $v_{i}v_{k}\in E(G)$ for $k\neq i,j$. Since the
$\mathrm{deg}_{G}(v_{i})=d_{i}-1\leq n-2$, we obtain that $(v_{i},v_{j})\notin
E(G)$. Let $X=\Gamma_{G}(v_{j})$ and write $d=|X|$. Since
$\mathrm{deg}_{G}(v_{j})=d_{j}+1>0$, we have $d\geq 1$.

Claim. There is $v_{k}\in X$ such that $(v_{k},v_{\ell})\notin E(G)$ for some
$\ell\neq k$.

###### Proof of the claim.

Assume on the contrary that $(v_{k},v_{\ell})\in E(G)$ for each $v_{k}\in X$
and $\ell\neq k$. Thus $\mathrm{deg}_{G}(v_{k})=n-1$ for each $v_{k}\in X$.
Since $v_{i},v_{j}\notin X$, it follows that
$d_{k}=\mathrm{deg}_{G}(v_{k})=n-1$ for each $v_{k}\in X$.

Let $H$ be a realization of the graphic sequence $D$ on the vertex set
$\\{v_{1},\dots,v_{n}\\}$. Since $\mathrm{deg}_{H}(v_{k})=d_{k}=n-1$ for each
$v_{k}k\in X$, and $v_{j}\notin X$, it follows that
$d_{j}=\mathrm{deg}_{H}(v_{j})\geq|X|=d$. But
$|X|=\mathrm{deg}_{G}(v_{j})=d_{j}+1$, so $d_{j}<|X|$. Contradiction, we
proved the Claim. ∎

By the Claim, we can fix $v_{k}\in X$ such that $(v_{k},v_{\ell})\notin E(G)$
for some $\ell\neq k$. Then $\ell\neq i,j$ since $v_{i}v_{k}$ and
$(v_{j},v_{k})$ are edges in $G$. Let

$G^{\prime}=G+(v_{i},v_{j})-(v_{j},v_{k})+(v_{k},v_{\ell}).$

Then $\mathbf{d}(G^{\prime})=D+1^{+j}_{+\ell}$. So $G^{\prime}$ satisfies the
requirements. Thus we could always define $G^{\prime}$.

Since there are less than $n^{2}$ edges and less than $n^{4}$ many paths of
length 3, for any $H\in\mathbb{G}(\mathcal{D}^{++})$ there are less than
$n^{2}+n^{4}$ many $G\in\mathbb{G}(\mathcal{D}^{+-})$ such that $G^{\prime}H$.
So we proved
$|\mathbb{G}(\mathcal{D}^{+-})|\leq(n^{4}+n^{2})\cdot|\mathbb{G}(\mathcal{D}^{++})|$.

The inequality
$|\mathbb{G}(\mathcal{D}^{+-})|\leq(n^{4}+n^{2})\cdot|\mathbb{G}(\mathcal{D}^{--})|$
can be proved analogously.

∎

######  Remark.

If $D$ is the constant 0 sequence of length $n$, then
$|\mathbb{G}(\mathcal{D}^{++})|>0$, but $|\mathbb{G}(\mathcal{D}^{+-})|=0$
because $\mathcal{D}^{+-}=\emptyset$, so in 6.2.(a), we can not omit
$|\mathcal{G}(D)|$ from the RHS of the inequality.