# Tight upper bound on the clique size in the square of 2-degenerate graphs

Seog-Jin Kim, Xiaopan Lian Department of Mathematics Education, Konkuk
University, Korea. E-mail<EMAIL_ADDRESS>Center for Combinatorics and
LPMC, Nankai University, China. _E-mail:_<EMAIL_ADDRESS>
###### Abstract

The square of a graph $G$, denoted $G^{2}$, has the same vertex set as $G$ and
has an edge between two vertices if the distance between them in $G$ is at
most $2$. In general, $\Delta(G)+1\leq\chi(G^{2})\leq\Delta(G)^{2}+1$ for
every graph $G$. Charpentier [1] asked whether $\chi(G^{2})\leq 2\Delta(G)$ if
$mad(G)<4$. But Hocquard, Kim, and Pierron [6] answered his question
negatively. For every even value of $\Delta(G)$, they constructed a
2-degenerate graph $G$ such that $\omega(G^{2})=\frac{5}{2}\Delta(G)$. Note
that if $G$ is a 2-degenerate graph, then $mad(G)<4$. Thus, we have that

${\displaystyle\frac{5}{2}\Delta(G)\leq\max\\{\chi(G^{2}):G\mbox{ is a
2-degenerate graph}\\}\leq 3\Delta(G)+1}.$

So, it was naturally asked whether there exists a constant $D_{0}$ such that
$\chi(G^{2})\leq\frac{5}{2}\Delta(G)$ if $G$ is a 2-degenerate graph with
$\Delta(G)\geq D_{0}$. Recently Cranston and Yu [3] showed that
$\omega(G^{2})\leq\frac{5}{2}\Delta(G)+72$ if $G$ is a 2-degenerate graph, and
$\omega(G^{2})\leq\frac{5}{2}\Delta(G)+60$ if $G$ is a 2-degenerate graph with
$\Delta(G)\geq 1729$. We show that there exists a constant $D_{0}$ such that
$\omega(G^{2})\leq\frac{5}{2}\Delta(G)$ if $G$ is a 2-degenerate graph with
$\Delta(G)\geq D_{0}$. This upper bound on $\omega(G^{2})$ is tight by the
construction in [6].

##  1 Introduction

The square of a graph $G$, denoted $G^{2}$, has the same vertex set as $G$ and
has an edge between two vertices if the distance between them in $G$ is at
most $2$. Let $\chi(G)$ be the chromatic number of a graph $G$, and let
$\omega(G)$ be the clique number of $G$. For every graph $G$, trivially
$\Delta(G)+1\leq\chi(G^{2})\leq\Delta(G)^{2}+1$.

Wegner [10] proposed the following conjecture.

######  Conjecture 1.1.

[10] Let $G$ be a planar graph. The chromatic number $\chi(G^{2})$ of $G^{2}$
is at most 7 if $\Delta(G)=3$, at most $\Delta(G)+5$ if $4\leq\Delta(G)\leq
7$, and at most $\lfloor\frac{3\Delta(G)}{2}\rfloor+1$ if $\Delta(G)\geq 8$.

Conjecture 1.1 is wide open. The only case for which we know tight bound is
when $\Delta(G)=3$. Thomassen [9] and, independently, Hartke, Jahanbekam, and
Thomas [5] showed that $\chi(G^{2})\leq 7$ if $G$ is a planar graph with
$\Delta(G)=3$, which proves Conjecture 1.1 for $\Delta(G)=3$. Even the upper
bound on $\omega(G^{2})$ was not known until this year. Cranston [4] showed
that $\omega(G^{2})\leq\lfloor\frac{3\Delta(G)}{2}\rfloor+1$ if $G$ is a
planar graph with $\Delta(G)\geq 34$. One may see the detailed story on the
study of Wegner’s conjecture in [2].

The maximum average degree of a graph $G$, denoted
$\operatorname{\mathrm{mad}}(G)$, is defined as $\max_{H\subseteq
G}\frac{2|E(H)|}{|V(H)|}$. A graph $G$ is $k$-degenerate if each subgraph of
$G$ contains a vertex of degree at most $k$. Equivalently, there exists a
vertex order $\sigma$ such that each vertex has at most $k$ neighbors later in
$\sigma$. Note that if $G$ is a 2-degenerate graph, then
$\operatorname{\mathrm{mad}}(G)<4$.

Recently, following problem was considered in [1] and has received some
attentions.

######  Problem 1.2 ([1]).

For each integer $k\geq 2$, what is
$\max\\{\chi(G^{2}):\operatorname{\mathrm{mad}}(G)<2k\\}$?

For $k=2$, Charpentier [1] conjectured that $\chi(G^{2})\leq 2\Delta(G)$ if
$\operatorname{\mathrm{mad}}(G)<4$, but it was disproved in [8] by
constructing a graph $G$ such that $\operatorname{\mathrm{mad}}(G)<4$ and
$\chi(G^{2})=2\Delta(G)+2$.

Furthermore, Hocquard, Kim, and Pierron [6] constructed a graph $G$ with
$\operatorname{\mathrm{mad}}(G)<4$ and $\omega(G^{2})=\frac{5}{2}\Delta(G)$
for every even value of $\Delta(G)$. They also showed that for every $G$ such
that $\operatorname{\mathrm{mad}}(G)<4$, the graph $G^{2}$ is
$3\Delta(G)$-degenerate. So in general we have the following bounds on
$\chi(G^{2})$.

$\frac{5}{2}\Delta(G)\leq\max\\{\chi(G^{2}):\operatorname{\mathrm{mad}}(G)<4\\}\leq
3\Delta(G)+1.$

So the following question was asked in [6].

######  Question 1.3.

[6] Does there exist $D_{0}$ such that every graph with $\Delta(G)\geq D_{0}$
and $mad(G)<4$ has $\chi(G^{2})\leq\frac{5}{2}\Delta(G)$?

Note that the construction in [6] is actually a 2-degenerate graph. So, the
following question was also asked in [6].

######  Question 1.4.

[6] Does there exist $D_{0}$ such that every 2-degenerate graph $G$ with
$\Delta(G)\geq D_{0}$ has $\chi(G^{2})\leq\frac{5}{2}\Delta(G)$?

In this direction, Cranston and Yu [3] showed the following interesting
theorem.

######  Theorem 1.5.

Fix a positive integer $D$. If a graph G is 2-degenerate with $\Delta(G)\leq
D$, then $\omega(G^{2})\leq\frac{5}{2}D+72$. Furthermore, if $G$ is a
2-degenerate graph with $D\geq 1729$, then $\omega(G^{2})\leq\frac{5}{2}D+60$.

Also it was proved in [3] that if $\operatorname{\mathrm{mad}}(G)<4$ and
$\Delta(G)\leq D$, then $\omega(G^{2})\leq\frac{5}{2}D+532$.

In this paper, we prove the following result.

######  Theorem 1.6.

There exists a constant $D_{0}>0$ such that for a positive integer $D$ with
$D\geq D_{0}$, if $G$ is a 2-degenerate graph with $\Delta(G)\leq D$, then
$\omega(G^{2})\leq\frac{5}{2}D$.

Note that $D_{0}=6\times(331\times 2+10\times{331\choose 2}+2000)=3,292,872$
in Theorem 1.6. And note that the upper bound on $\omega(G^{2})$ in Theorem
1.6 is tight by the construction in [6].

This paper is organized as follows. In Section 2, we explain important results
that were proved in [3]. In Section 3, we give the proof of Theorem 1.6.

##  2 Preliminaries

In this section, first we provide the construction of
$\omega(G^{2})=\frac{5}{2}\Delta(G)$.

######  Construction 2.1.

[6] Fix a positive integer $D=4k+r$ where $k,r$ are positive integers with
$k\geq 2$ and $0\leq r\leq 3$. We form graph $G_{D}$ as follows. Let $i$ and
$j$ be positive integers with $1\leq i<j\leq 5$.

  1. (1)

Start with the complete graph $K_{5}$ on vertex set
$\\{u_{1},\ldots,u_{5}\\}$.

  2. (2)

If $r=0$, then replace each edge $u_{i}u_{j}$ of $K_{5}$ with a copy of
$K_{2,k}$, identifying the vertices in the part of size 2 with $u_{i}$ and
$u_{j}$ for each $1\leq i<j\leq 5$;

If $r=1$, then replace $u_{i}u_{j}\in\\{u_{1}u_{2},u_{3}u_{4}\\}$ with a copy
of $K_{2,k+1}$ and replace each edge $u_{i}u_{j}\in
E(K_{5})\setminus\\{u_{1}u_{2},u_{3}u_{4}\\}$ with a copy of $K_{2,k}$,
identifying the vertices in the part of size 2 with $u_{i}$ and $u_{j}$ for
each $1\leq i<j\leq 5$;

If $r=2$, then replace each edge
$u_{i}u_{j}\in\\{u_{1}u_{2},u_{2}u_{3},u_{3}u_{4},u_{4}u_{5},u_{5}u_{1}\\}$
with a copy of $K_{2,k+1}$ and replace each edge $u_{i}u_{j}\in
E(K_{5})\setminus\\{u_{1}u_{2},u_{2}u_{3},u_{3}u_{4},u_{4}u_{5},u_{5}u_{1}\\}$
with a copy of $K_{2,k}$, identifying the vertices in the part of size 2 with
$u_{i}$ and $u_{j}$ for each $1\leq i<j\leq 5$;

If $r=3$, then replace each edge $u_{i}u_{j}\in\\{u_{1}u_{2},u_{3}u_{4}\\}$
with a copy of $K_{2,k+2}$, replace each edge
$u_{i}u_{j}\in\\{u_{2}u_{3},u_{4}u_{5},u_{5}u_{1}\\}$ with a copy of
$K_{2,k+1}$, and replace each edge $u_{i}u_{j}\in
E(K_{5})\setminus\\{u_{1}u_{2},u_{2}u_{3},u_{3}u_{4},u_{4}u_{5},u_{5}u_{1}\\}$
with a copy of $K_{2,k}$, identifying the vertices in the part of size 2 with
$u_{i}$ and $u_{j}$ for each $1\leq i<j\leq 5$;

We denote by $V_{e}$ the $k$, $k+1$ or $k+2$ vertices added while replacing
the edge $e$ of $K_{5}$.

  3. (3)

Now for each pair, $x$ and $y$, of vertices of degree 2 with no common
neighbor, add a vertex $z_{xy}$ adjacent to both $x$ and $y$.

Call the resulting graph $G_{D}$ (see Figure 1).

Observe that $G_{D}$ is 2-degenerate with
$\omega(G^{2}_{D})=\lfloor\frac{5}{2}D\rfloor$ and $\Delta(G_{D})=D$. Note
that when $r\in\\{0,2\\}$, this is the degree of vertices of the original
$K_{5}$ and every other vertex has degree no more than $D$. When
$r\in\\{1,3\\}$, this is the degree of all vertices but $u_{5}$ of the
original $K_{5}$ and every other vertex has degree no more than $D$.)
Moreover, the vertices in $\bigcup_{e\in E(K_{5})}V_{e}$ induce a clique of
size $\lfloor\frac{5}{2}D\rfloor$ in $G^{2}_{D}$.

Figure 1: Black vertices induce a clique in $G^{2}_{D}$

Next, we introduce a definition used in [3].

######  Definition 2.2.

A graph $G$ is nice w.r.t. a clique $S$ in $G^{2}$, if the following (1), (2),
and (3) hold.

  1. (1)

$S$ is a clique in $G^{2}$,

  2. (2)

$S$ is an independent set in $G$, and

  3. (3)

$G$ has a 2-degeneracy order $\sigma$ such that all vertices of $S$ appear
consecutively in $\sigma$.

Note that the notion in Definition 2.2 is inspired by the construction in [6]
(Figure 1). And the following two theorems were proved in [3].

######  Theorem 2.3.

[3] If $G$ is nice w.r.t. a maximum clique $S$ in $G^{2}$ and $\Delta(G)\leq
D$, then $\omega(G^{2})\leq\frac{5}{2}D$.

Fix a positive integer $D$. Let $f(D)$ be the maximum size of a clique $S$ in
the square of a 2-degenerate graph $G$ with $\Delta(G)\leq D$. Then we have
the following important property.

######  Theorem 2.4.

([3],Theorem 5) For every positive integer $D\geq 1729$, some 2-degenerate
graph $G$ with $\Delta(G)\leq D$ is nice w.r.t. a clique $S$ in $G^{2}$ and
$|S|\geq f(D)-60$.

Note that Theorem 1.5 comes from Theorem 2.3 and Theorem 2.4. We also use
Theorem 2.4 in our proof of the main theorem. But, in Theorem 2.4, the authors
of [3] assumed that $f(D)\geq\frac{5}{2}D+60$ which is slightly different from
our assumption that $f(D)>\frac{5}{2}D$. So, we modify the values in
calculations in the proof of Theorem 2.5 and we have the following theorem.

######  Theorem 2.5.

For every positive integer $D\geq 1733$, if a 2-degenerate graph $G$ with
$\Delta(G)\leq D$ satisfies $\omega(G^{2})=f(D)>\frac{5}{2}D$, then there is a
subgraph $G^{*}$ of $G$ which is nice w.r.t. a clique $S^{*}$ in
${(G^{*})}^{2}$ and $|S^{*}|\geq f(D)-60$.

For completeness of the proof, we provide the proof of Theorem 2.5 in the
appendix. However, we shall emphasize that the proof of Theorem 2.5 is exactly
that of Theorem 5 in [3]. The proof of Theorem 2.5 just follows the proof of
Theorem 5 in [3].

##  3 Proof of Theorem 1.6

Let $D_{0}:=6\times(331\times 2+10\times{331\choose 2}+2000)$. Suppose that
for an integer $D\geq D_{0}$, there exists a 2-degenerate graph $G$ with
$\Delta(G)\leq D$ such that $G^{2}$ has a clique $S$ of order $f(D)$ where
$f(D)>\frac{5}{2}D$. Throughout this section, let $G$ be a counterexample to
Theorem 1.6 minimizing $|V(G)|+|E(G)|$.

Let $\sigma$ be a vertex order witnessing that $G$ is 2-degenerate. Choose
$\sigma$ so that the first vertex in $S$ appears as late as possible (each
vertex has at most two neighbors later in the order $\sigma$). Since $G$ is a
minimal counterexample, every edge in $E(G)$ has an endpoint in $S$. Hence, by
the proof of Theorem 2.5, there is a triple $(G^{*},S^{*},\sigma^{*})$
obtained from $(G,S,\sigma)$ such that

  1. (a)

$S^{*}\subseteq S$ and $|S\setminus S^{*}|\leq 60$,

  2. (b)

$G^{*}$ is obtained from $G$ by deleting every edge of $G$ whose endpoints are
both outside $S^{*}$,

  3. (c)

$S^{*}$ is a clique in $(G^{*})^{2}$,

  4. (d)

$G^{*}$ is nice w.r.t. $S^{*}$ where the order $\sigma^{*}$ satisfies that all
vertices of $S^{*}$ appear consecutively in $\sigma^{*}$, and

  5. (e)

both of $V(G^{*})\setminus S^{*}$ and $S^{*}$ are independent sets in $G^{*}$.

Let $s^{*}:=|S^{*}|$.

######  Remark 3.1.

Note that by Theorem 2.3, we have that $s^{*}\leq\frac{5}{2}D$. By (a) and our
assumption that $|S|>\frac{5}{2}D$, we have that $s^{*}>\frac{5}{2}D-60$.
Thus, $\frac{5}{2}D-60<s^{*}\leq\frac{5}{2}D$.

Note that throughout the paper, the bounds on $s^{*}$ are
$\frac{5}{2}D-60<s^{*}\leq\frac{5}{2}D$.

Next, we define $R^{*}$ and $T^{*}$ as follows.

######  Definition 3.2.

Let $T^{*}\subset V(G^{*})$ be the set of vertices which are vertices after
$S^{*}$ in $\sigma^{*}$ and have at least one neighbor in $S^{*}$ in the graph
$G^{*}$. Let $R^{*}=V(G^{*})\setminus(S^{*}\cup T^{*})$.

######  Remark 3.3.

Observe that for each $v\in V(G)$, we have $N_{G}(v)\cap
S^{*}=N_{G^{*}}(v)\cap S^{*}$. Furthermore, for each $v\in S^{*}$, we have
that $N_{G^{*}}(v)=N_{G}(v)$. And since $G^{*}$ is 2-degenerate, by the
definition of $R^{*}$, for each $v\in R^{*}$, we have that $|N_{G}(v)\cap
S^{*}|=|N_{G^{*}}(v)\cap S^{*}|\leq 2$.

[Outline of the proof Theorem 1.6]

  * •

If $f(D)>\frac{5}{2}D$, then we have that $|S\setminus S^{*}|\leq 60$ by
Theorem 2.5. Also, by Theorem 2.3, we have that $|S^{*}|\leq\frac{5}{2}D$. So,
our assumption is that $\frac{5}{2}D-60<|S^{*}|\leq\frac{5}{2}D$.

  * •

We establish an observation regarding the size of $T^{*}$ and show that
$|T^{*}|=6$. For this, we define an auxiliary multigraph, denoted $H^{*}$,
with $|S^{*}|=|E(H^{*})|$ and $T^{*}=V(H^{*})$.

  * •

If $|T^{*}|\geq 7$, then we show that $H^{*}$ has a very small degree vertex,
which leads a contradiction. This implies that $|T^{*}|\leq 6$. Next, we show
that $|T^{*}|\geq 5$ by simple counting argument. Finally, we show that if
$|T^{*}|=5$, then the graph $G$ has a vertex $v$ with $d_{G}(v)>D$, which is a
contradiction. Thus we conclude that $|T^{*}|=6$.

  * •

Let $H_{0}^{*}$ be the underlying simple graph of $H^{*}$. In Subsectin 3.2,
we show that $H_{0}^{*}$ is a complete graph when $|T^{*}|=6$.

  * •

From the fact that $H_{0}^{*}$ is a complete graph, we show that the
multigraph $H^{*}$ is almost balanced. That is, each vertex $v\in T^{*}$ has
$\frac{5}{6}D-c_{1}\leq d_{H^{*}}(v)\leq\frac{5}{6}D+c_{1}^{\prime}$, and the
multiplicity of each edge $uv$ in $H^{*}$ satisfies that
$\mu(uv)\geq\frac{D}{6}-c_{2}$ where $c_{1}$, $c_{1}^{\prime}$ and $c_{2}$ are
small enough compared to $D$.

  * •

For each $1\leq i<j\leq 6$, let $S_{i,j}$ be the set of vertices in
$S\setminus(S^{*}\cup\\{v_{i},v_{j}\\})$ that are adjacent to neither $v_{i}$
nor $v_{j}$ where $v_{i},v_{j}\in T^{*}$, and let $s_{i,j}=|S_{i,j}|$. Next,
from careful analysis, we obtain inequality ($\mathcal{D}$) after proving
Claim 3.23.

$\sum_{1\leq i<j\leq 6}s_{i,j}\leq\left(\frac{5}{2}D-s^{*}\right)-30.$

And then, we finish the proof of Theorem 1.6 with careful analysis.

###  3.1 Basic framework

In this subsection, we study the properties in $T^{*}$ and show that
$|T^{*}|=6$. First, we show that $T^{*}\neq\emptyset$ in Claim 3.4. Then, we
give a rough bound on the degree of vertices in the graph $G^{*}$ in Claim
3.5. Note that the information given by Claim 3.4 and Claim 3.5 is not
sufficient to conclude that $|T^{*}|=6$. Therefore, we introduce an important
auxiliary multigraph, denoted $H^{*}$, obtained from $G^{*}$ which satisfies
that $V(H^{*})=T^{*}$ and $|E(H^{*})|=s^{*}$. Next, in Claim 3.9, we
investigate some properties of the multigraph $H^{*}$. Finally, using these
properties of the multigraph $H^{*}$, we show in Claim 3.11 that $|T^{*}|=6$.

######  Claim 3.4.

$T^{*}\neq\emptyset$.

###### Proof.

Suppose that $T^{*}=\emptyset$. Recall that $S^{*}$ is an independent set in
$G^{*}$, so each edge in $(G^{*})^{2}[S^{*}]$ comes via a vertex in $R^{*}$.
But each vertex $v\in S^{*}$ has at most $D$ neighbors $w$ in $R^{*}$ and and
each such $w$ creates an adjacency in $(G^{*})^{2}$ between $v$ and at most
one vertex $v^{\prime}$ in $S^{*}$, since $w$ has at most tow neighbors in
$S^{*}$. Then by $(d)$, we have that $|S^{*}|\leq D+1$. This is a
contradiction since $s^{*}>\frac{5}{2}D-60>D+1$. ∎

By analyzing the adjacencies between vertices in $T^{*}$ and $S^{*}$ in the
graph $G^{*}$, we prove that for each vertex $v\in T^{*}$, the size of
$N_{G^{*}}(v)\cap S^{*}$ is somehow large. It helps us to prove that the order
of $T^{*}$ is bounded by combining Theorem 2.3 and the handshaking lemma. We
now prove the following claim.

######  Claim 3.5.

  * (1)

For each $v\in S^{*}$, $|N_{G^{*}}(v)\cap T^{*}|=2$.

  * (2)

For each $v\in T^{*}$, $|N_{G^{*}}(v)\cap S^{*}|\geq\frac{D}{2}-57$.

###### Proof.

(1) Suppose that there is a vertex $v\in S^{*}$ such that $|N_{G^{*}}(v)\cap
T^{*}|\leq 1$. First note that $\Delta(G^{*})\leq D$. Then since $S^{*}$ is an
independent set, $v$ has at most $D-1$ neighbors in $R^{*}$ and each of these
neighbors has at most one neighbor in $S^{*}$ other than $v$ since $G^{*}$ is
2-degenerate. And if $w\in N_{G^{*}}(v)\cap T^{*}$, then $w$ has at most $D-1$
neighbors distinct from $v$ in $S^{*}$. Thus, by (c), we have that

$\displaystyle s^{*}$ $\displaystyle=$ $\displaystyle|N_{{(G^{*})}^{2}}(v)\cap
S^{*}|+1\leq|N_{G^{*}}(v)\cap R^{*}|+|N_{G^{*}}(w)\cap S^{*}|+1$
$\displaystyle\leq$ $\displaystyle D-1+D-1+1=2D-1<\frac{5}{2}D-60,$

a contradiction.

(2) Suppose that there is a vertex $v\in T^{*}$ such that $|N_{G^{*}}(v)\cap
S^{*}|<\frac{D}{2}-57$. Let $u$ be a vertex in $N_{G^{*}}(v)\cap S^{*}$. By
(1), $u$ has at most one neighbor, say $w$, distinct from $v$ in $T^{*}$. Then
by (c) and $\Delta(G^{*})\leq D$,

$\displaystyle s^{*}$ $\displaystyle=$ $\displaystyle|N_{{(G^{*})}^{2}}(u)\cap
S^{*}|+1\leq|N_{G^{*}}(u)\cap R^{*}|+|N_{G^{*}}(v)\cap
S^{*}|+|N_{G^{*}}(w)\cap S^{*}|$ $\displaystyle<$ $\displaystyle
D-2+\frac{D}{2}-57+D-1=\frac{5}{2}D-60,$

a contradiction. ∎

In the following, we show that the size of $T^{*}$ is bounded. We prove this
by constructing an auxiliary mulitigraph $H^{*}$ obtained from $G^{*}$.

######  Construction 3.6.

Form $H^{*}$ from $G^{*}$ as follows: delete all vertices of $R^{*}$ and
contract one edge incident to each vertex of $S^{*}$.

Note that, by Claim 3.5 and Construction 3.6, the following holds.

$V(H^{*})=T^{*}$, $|E(H^{*})|=|S^{*}|=s^{*}$, and $\Delta(H^{*})\leq D$.

We define $H^{*}_{0}$, $\bar{H^{*}_{0}}$, $E(v)$, and $\mu(uv)$ as follows.

######  Definition 3.7.

Denote by $H^{*}_{0}$ the underlying simple graph of $H^{*}$ and denote by
$\bar{H^{*}_{0}}$ the complement of $H^{*}_{0}$. For $v\in T^{*}$, let $E(v)$
be the set of edges in $H^{*}$ that is incident with $v$. For an edge $uv\in
E(H^{*})$, let $\mu(uv)$ be the miltiplicity of $uv$ in $H^{*}$.

First, we show the following key observation.

######  Remark 3.8.

Since $\Delta(G^{*})\leq D$, for each $v\in S^{*}$, $v$ has at most $D-2$
neighbors in $R^{*}$ by Claim 3.5 (1). Thus, the edge in $H^{*}$ arising from
$v$ has a common endpoint with all edges of $H^{*}$ except for at most $D-2$
edges. In other words, for every edge $uv$ in $H^{*}$, we have that
$|E(H^{*})\setminus(E(u)\cup E(v))|\leq D-2$.

We proceed by analyzing the adjacency between vertices in $H^{*}$. First, we
establish the following claim.

######  Claim 3.9.

The following holds.

  1. (1)

For each $uv\in E(H^{*})$, $d_{H^{*}}(u)+d_{H^{*}}(v)-\mu(uv)\geq s^{*}-D+2$.

  2. (2)

For each $v\in T^{*}$, $|N_{H^{*}}(v)|\geq 2$.

  3. (3)

For each $v\in T^{*}$ and $w\in N_{H^{*}}(v)$, ${\displaystyle\sum_{u\in
N_{H^{*}}(v)\setminus\\{w\\}}\mu(uv)\geq s^{*}-2D+2}$.

  4. (4)

For each $v\in T^{*}$,
$d_{H^{*}}(v)\geq\frac{|N_{H^{*}}(v)|(s^{*}-2D+2)}{|N_{H^{*}}(v)|-1}$.

###### Proof.

  * (1)

By Remark 3.8, we have that

$D-2\geq|E(H^{*})\setminus(E(u)\cup
E(v))|=|E(H^{*})|-(d_{H^{*}}(u)+d_{H^{*}}(v)-\mu(vw)).$

So, $d_{H^{*}}(u)+d_{H^{*}}(v)-\mu(uv)\geq s^{*}-D+2$.

  * (2)

Suppose, to the contrary, that there is a vertex $v$ in $T^{*}$ such that
$|N_{H^{*}}(v)|=1$. Let $N_{H^{*}}(v)=\\{u\\}$. Then, by (1), we have that

$d_{H^{*}}(u)+d_{H^{*}}(v)-\mu(uv)=d_{H^{*}}(u)\geq
s^{*}-D+2>\frac{5}{2}D-60-D+2>D,$

a contradiction since each vertex in $H^{*}$ has degree at most $D$.

  * (3)

Let $v\in T^{*}$ and $w\in N_{H^{*}}(v)$. By (1), we have that

$d_{H^{*}}(v)+d_{H^{*}}(w)-\mu(vw)=d_{H^{*}}(w)+\sum_{u\in
N_{H^{*}}(v)\setminus\\{w\\}}\mu(uv)\geq s^{*}-D+2.$

Since $\Delta(H^{*})\leq D$, we have that ${\displaystyle\sum_{u\in
N_{H^{*}}(v)\setminus\\{w\\}}\mu(uv)\geq s^{*}-2D+2}$.

  * (4)

Let $v\in T^{*}$. By (3), we have that

$\displaystyle|N_{H^{*}}(v)|(s^{*}-2D+2)$ $\displaystyle\leq\sum_{w\in
N_{H^{*}}(v)}\sum_{u\in N_{H^{*}}(v)\setminus\\{w\\}}\mu(uv)$
$\displaystyle=(|N_{H^{*}}(v)|-1)\sum_{w\in N_{H^{*}}(v)}\mu(vw)$
$\displaystyle=(|N_{H^{*}}(v)|-1)d_{H^{*}}(v).$

Therefore,
$d_{H^{*}}(v)\geq\frac{|N_{H^{*}}(v)|(s^{*}-2D+2)}{|N_{H^{*}}(v)|-1}$.

∎

Note that when $|T^{*}|=6$, we have that the lower bound on the degrees of
vertices in $H^{*}$ given by Claim 3.9(4) is better than that in Claim 3.5 as
$D\geq D_{0}$ is large enough. Now, we prove that $|V(H^{*})|=6$.

######  Claim 3.10.

$H^{*}$ is a connected graph with $|T^{*}|\leq 6$.

###### Proof.

First, we show that $H^{*}$ is a connected graph. Suppose that $H^{*}$ is
disconnceted. By Claim 3.9(2), $H^{*}$ has no isolated vertices. Thus, each
component of $H^{*}$ contains at least one edge. Hence, there is a component
$H^{\prime}$ of $H^{*}$ which has at most $\frac{|E(H^{*})|}{2}$ edges. Then
there are at least $\frac{|E(H^{*})|}{2}=\frac{s^{*}}{2}>D-2$ edges that are
disjoint from edges in $H^{\prime}$, contradicting Remark 3.8.

Now, we show that $|T^{*}|\leq 6$. Suppose that $|T^{*}|\geq 7$. Then there is
a vertex $v\in T^{*}$ with

$d_{H^{*}}(v)\leq\frac{2|E(H^{*})|}{|T^{*}|}\leq\frac{2s^{*}}{7}<\frac{3(s^{*}-2D+2)}{2}<\frac{11}{14}D-60.$

Since $d_{H^{*}}(v)<\frac{3(s^{*}-2D+2)}{2}$, by Claim 3.9(4), we have that
$|N_{H^{*}}(v)|\geq 4$.

Let $A$ be the set of all vertices in $H^{*}$ that are of degree at least
$\frac{11}{14}D-60$. For each $w\in N_{H^{*}}(v)$, by Claim 3.9(1), we have

$d_{H^{*}}(w)\geq s^{*}-D+2-d_{H^{*}}(v)\geq
s^{*}-D+2-\frac{2s^{*}}{7}>\frac{5}{7}\left(\frac{5}{2}D-60\right)-D+2\geq\frac{11}{14}D-60.$

It implies that $N_{H^{*}}(v)\subseteq A$. Thus, $|A|\geq|N_{H^{*}}(v)|\geq
4$. We proceed by show that if $|A|\geq 4$, then there is a vertex in $H^{*}$
with degree at most $\frac{2}{3}s^{*}-\frac{22}{21}D+80$ which is smaller than
$\frac{2s^{*}}{7}$.

Note that by the handshaking lemma, we have $|A|<7$. Therefore, there is a
vertex $v^{\prime}\in T^{*}$(it may happen that $v^{\prime}=v$) with

$\displaystyle d_{H^{*}}(v^{\prime})$
$\displaystyle\leq\frac{2|E(H^{*})|-|A|(\frac{11}{14}D-60)}{|T^{*}|-|A|}$
$\displaystyle\leq\frac{2s^{*}-4(\frac{11}{14}D-60)}{3}$
$\displaystyle=\frac{2}{3}s^{*}-\frac{22}{21}D+80$
$\displaystyle<\frac{3(s^{*}-2D+2)}{2}$ $\displaystyle<\frac{11}{14}D-60.$

Again, for each $w^{\prime}\in N_{H^{*}}(v^{\prime})$, by Claim 3.9(1), we
have that

$d_{H^{*}}(w^{\prime})\geq s^{*}-D+2-d_{H^{*}}(v^{\prime})\geq
s^{*}-D+2-\frac{2}{3}s^{*}+\frac{22}{21}D-80\geq\frac{s^{*}}{3}+\frac{D}{21}-78>\frac{11}{14}D-60.$

Moreover, since $d_{H^{*}}(v^{\prime})<\frac{3(s^{*}-2D+2)}{2}$, by Claim
3.9(4), we have that $|N_{H^{*}}(v^{\prime})|\geq 4$. Also, we deduce that
$N_{H^{*}}(v^{\prime})\subseteq A$. Note that by Claim 3.5(2), we have that
$d_{H^{*}}(v^{\prime})\geq\frac{D}{2}-57$. Thus, there is a vertex $u\in
T^{*}\setminus(A\cup\\{v^{\prime}\\})$ with

$\displaystyle d_{H^{*}}(u)$
$\displaystyle\leq\frac{2s^{*}-4(\frac{s^{*}}{3}+\frac{D}{21}-78)-(\frac{D}{2}-57)}{2}$
$\displaystyle\leq\frac{1}{3}s^{*}-\frac{2}{21}D+2\times
78-\frac{D}{4}+\frac{57}{2}$
$\displaystyle\leq\frac{1}{3}\times\frac{5}{2}D-\frac{2}{21}D-\frac{D}{4}+156+\frac{57}{2}$
$\displaystyle=\frac{41}{84}D+184.5$ $\displaystyle<\frac{D}{2}-57.$

This is a contradiction to Claim 3.5(2), and thus $|T^{*}|\leq 6$. ∎

######  Claim 3.11.

$H^{*}$ is a connected graph with $|T^{*}|=6$.

###### Proof.

By Claim 3.10, it suffices to show that $|T^{*}|>5$. Note that each vertex in
$H^{*}$ is of degree at most $D$. So, we have that

$D|T^{*}|\geq\sum_{v\in T^{*}}d_{H^{*}}(v)=2s^{*},$

which implies that $|T^{*}|\geq 5.$ Thus, $5\leq|T^{*}|\leq 6$.

Next, we show that $|T^{*}|=6$. We will show that there exists a contradiction
if $|T^{*}|=5$. From now on, we suppose that $|T^{*}|=5$. Recall that by
Remark 3.3, we have that $\sum_{w\in S^{*}}|N_{G}(w)\cap T^{*}|=\sum_{w\in
S^{*}}|N_{G^{*}}(w)\cap T^{*}|=2s^{*}$. Thus,

$\displaystyle\sum_{v\in T^{*}}d_{G}(v)$ $\displaystyle=\sum_{w\in
S^{*}}|N_{G}(w)\cap T^{*}|+\sum_{w\in R^{*}\cup T^{*}}|N_{G}(v)\cap T^{*}|$
$\displaystyle=2s^{*}+\sum_{w\in R^{*}\cup T^{*}}|N_{G}(v)\cap T^{*}|$
$\displaystyle<5D,$

which implies that

$\sum_{w\in R^{*}\cup T^{*}}|N_{G}(v)\cap
T^{*}|<5D-2s^{*}=2\left(\frac{5}{2}D-s^{*}\right)<2|S\setminus S^{*}|.$ (1)

If we can show that

$2|S\setminus S^{*}|\leq\sum_{w\in R^{*}\cup T^{*}}|N_{G}(v)\cap T^{*}|,$

then we can conclude that $|T^{*}|=6$ since by inequality (1), we have the
following contradiction

$2|S\setminus S^{*}|\leq\sum_{w\in R^{*}\cup T^{*}}|N_{G}(v)\cap
T^{*}|<2|S\setminus S^{*}|.$

We proceed by showing an even stronger version that $|N_{G}(v)\cap T^{*}|\geq
2$ for each $v\in S\setminus S^{*}$. We formalize this as a subclaim.

######  Claim 3.11.1.

If $v\in S\setminus S^{*}$, then $|N_{G}(v)\cap T^{*}|\geq 2$.

###### Proof.

Suppose that there is a vertex $v\in S\setminus S^{*}$ such that
$|N_{G}(v)\cap T^{*}|\leq 1$. Recall that Remark 3.3, for each $u\in R^{*}$,
we have that $|N_{G}(u)\cap S^{*}|=|N_{G^{*}}(u)\cap S^{*}|\leq 2$. For
$i\in[2]$, let $Y_{i}:=\\{w\in N_{G}(v)\setminus T^{*}:~{}|N_{G}(w)\cap
S^{*}|=i\\}$. We claim that $|Y_{2}|\leq 2(|T^{*}|+1)$.

Since $G$ is 2-degenerate, there are at most two vertices in
$N_{G}(v)\setminus T^{*}$ that are after $v$ in the order $\sigma$. We define
$X_{1}$ and $X_{2}$ as follows.

$\displaystyle X_{1}$ $\displaystyle:=$ $\displaystyle\\{w\in
N_{G}(v)\setminus T^{*}:~{}|N_{G}(w)\cap S^{*}|=2~{}\text{and}~{}v\text{~{}is
later than}~{}w~{}\text{in the order}~{}\sigma\\},\mbox{ and }$ $\displaystyle
X_{2}$ $\displaystyle:=$ $\displaystyle\\{w\in N_{G}(v)\setminus
T^{*}:~{}|N_{G}(w)\cap S^{*}|=2~{}\text{and}~{}w\text{~{}is later
than}~{}v~{}\text{in the order}~{}\sigma\\}.$

Then $Y_{2}=X_{1}\cup X_{2}$ and $|X_{2}|\leq 2$. Thus, it suffices to show
that $|X_{1}|\leq 2|T^{*}|$.

Figure 2: The occurrences of partial vertices of $G$ w.r.t $\sigma$.

For $w\in X_{1}$, let $\\{w_{1},w_{2}\\}=N_{G^{*}}(w)\cap S^{*}$. Then by
Remark 3.3 with $w\in R^{*}$, we have that $\\{w_{1},w_{2}\\}=N_{G}(w)\cap
S^{*}$. Since $\sigma$ is a 2-degeneracy order of $G$ and $v$ is later than
$w$ in $\sigma$, without loss of generality, say $w_{1}$ is before $w$ in the
order $\sigma$. Since $w_{1}\in S^{*}$, we have that $|N_{G^{*}}(w_{1})\cap
T^{*}|=2$ by Claim 3.5 (1). Let $\\{u_{1},u_{2}\\}=N_{G^{*}}(w_{1})\cap
T^{*}$. Again by Remark 3.3 with $w_{1}\in S^{*}$, we have that
$\\{u_{1},u_{2}\\}=N_{G}(w_{1})\cap T^{*}$. Since $\sigma$ is a 2-degeneracy
order of $G$ and $w$ is later than $w_{1}$ in $\sigma$, without loss of
generality, say that $u_{1}$ is before $w_{1}$ in the order $\sigma$ of $G$.
Hence, for each $w\in X_{1}$, there is a path $P_{w}:=u_{1}w_{1}wv$ contained
in $G$ where the occurrences of $u_{1},w_{1},w,v$ in the path $P_{w}$ are in
the same order as their occurrences in the order $\sigma$ of $G$ where
$u_{1}\in T^{*}$, as shown in Figure 2.

Since $\sigma$ is a 2-degeneracy order of $G$, for each vertex $x$ in $T^{*}$,
there are at most two vertices later than $x$ in the order $\sigma$. Thus,
$|X_{1}|\leq 2|T^{*}|$. Hence, $|Y_{2}|\leq|X_{1}|+|X_{2}|\leq 2(|T^{*}|+1)$.

Since $v\in S\setminus S^{*}$ and $|N_{G}(v)\cap T^{*}|\leq 1$, we have that

$\displaystyle s^{*}$ $\displaystyle=|S^{*}|=|N_{G^{2}}(v)\cap S^{*}|$
$\displaystyle=|N_{G}(v)\cap S^{*}|+|Y_{1}|+2|Y_{2}|+\left|\bigcup_{u\in
N_{G}(v)\cap T^{*}}(N_{G}(u)\cap S^{*})\right|$ $\displaystyle=(|N_{G}(v)\cap
S^{*}|+|Y_{1}|+|Y_{2}|)+|Y_{2}|+\left|\bigcup_{u\in N_{G}(v)\cap
T^{*}}(N_{G}(u)\cap S^{*})\right|$ $\displaystyle\leq
d_{G}(v)+|Y_{2}|+\left|\bigcup_{u\in N_{G}(v)\cap T^{*}}(N_{G}(u)\cap
S^{*})\right|$ $\displaystyle\leq d_{G}(v)+2(|T^{*}|+1)+\left|\bigcup_{u\in
N_{G}(v)\cap T^{*}}(N_{G}(u)\cap S^{*})\right|\quad\quad\quad\quad\quad~{}$
$\displaystyle\leq D+14+D$ $\displaystyle<\frac{5}{2}D-60,$

a contradiction. This completes the proof of Claim 3.11.1. ∎

Therefore, $|T^{*}|=6$. This completes the proof of Claim 3.11. ∎

###  3.2 $H^{*}_{0}$ is a complete graph if $|T^{*}|=6$

In this subsection, we prove that if the size of $T^{*}$ is 6, then the graph
$H^{*}_{0}$ is a complete graph. This helps us to further analyze the degree
of each vertex in the graph $H^{*}_{0}$. We first establish two useful claims,
Claim 3.12 and Claim 3.13, which are respectively about the minimum degree of
the graph $H^{*}_{0}$ and the sum of multiplicities of edges between some
special vertices of $H^{*}$. Then, by using these two claims and constructing
some multigraphs based on $H^{*}_{0}$, we prove that $\bar{H^{*}_{0}}$ is
triangle free in Claim 3.15. Lastly, we finish the proof that $H^{*}_{0}$ is a
complete graph in Claim 3.16.

Let $T^{*}=\\{v_{1},\ldots,v_{6}\\}$ in this subsection and the next
subsection.

To enhance the clarity of the proof of Claim 3.12, we begin by providing a
general outline before delving into the formal proof. We assume that
$N_{H^{*}_{0}}(v_{1})=\\{v_{2},v_{6}\\}$. By Claim 3.9(4), we deduce that
$d_{H^{*}}(v_{1})\geq 2s^{*}-4D+4$, which is close to $D$. Consequently, the
adjacencies between vertices in $T^{*}\setminus{v_{1}}$ are somewhat
constrained. First, we show that the set $\\{v_{3},v_{4},v_{5}\\}$ cannot form
an independent set in $H^{*}_{0}$ when $d_{H^{*}_{0}}(v_{1})=2$. Next, we show
that $\\{v_{3},v_{4},v_{5}\\}$ induces a triangle in $H^{*}_{0}$ under this
condition. And then, we finish the proof in Claim 3.16.

######  Claim 3.12.

For each $v\in T^{*}$, $d_{H^{*}_{0}}(v)\geq 3$.

###### Proof.

Without loss of generality, by Claim 3.9(2), we may assume that
$d_{H^{*}_{0}}(v_{1})=2$ and $N_{H^{*}_{0}}(v_{1})=\\{v_{2},v_{6}\\}$. Then by
Claim 3.9(4), $d_{H^{*}}(v_{1})\geq 2s^{*}-4D+4$. We first prove that
$\\{v_{3}v_{4},v_{4}v_{5},v_{3}v_{5}\\}\subseteq E(H^{*}_{0})$.

Suppose that $\\{v_{3},v_{4},v_{5}\\}$ is an independent set. Then
$d_{H^{*}_{0}}(v_{i})=2$ for each $i\in\\{3,4,5\\}$. Thus, by Claim 3.9(4),
for each $i\in\\{3,4,5\\}$ and $j\in\\{2,6\\}$, $v_{i}v_{j}\in E(H^{*}_{0})$
and $d_{H^{*}}(v_{i})\geq 2s^{*}-4D+4$. Hence, from $\sum_{v\in
T^{*}}d_{H^{*}}(v)=2{s^{*}}$, we have that

$d_{H^{*}}(v_{2})+d_{H^{*}}(v_{6})\leq
2s^{*}-4(2s^{*}-4D+4)=16D-6s^{*}-16<s^{*}-D+2.$ (2)

Recall that by Claim 3.9(1), for each $uv\in E(H^{*})$, we have that
$d_{H^{*}}(u)+d_{H^{*}}(v)-\mu(uv)\geq s^{*}-D+2$. Since
$d_{H^{*}}(v_{2})+d_{H^{*}}(v_{6})<s^{*}-D+2$, we have that $v_{2}v_{6}\notin
E(H^{*}_{0})$ which implies that
$d_{H^{*}_{0}}(v_{2})=d_{H^{*}_{0}}(v_{6})=4$. On the other hand, from
inequality (2) above, there exists $i\in\\{2,6\\}$ such that
$d_{H^{*}}(v_{i})\leq 8D-3s^{*}-8$. Since $d_{H^{*}_{0}}(v_{i})=4$, by Claim
3.9(4), $d_{H^{*}}(v_{i})\geq\frac{4(s^{*}-2D+2)}{3}$, which is a
contradiction since $\frac{4(s^{*}-2D+2)}{3}>8D-3s^{*}-8$.

Therefore, $\\{v_{3},v_{4},v_{5}\\}$ is not an independent set in $H^{*}_{0}$.
So, without loss of generality, assume that $v_{3}v_{4}\in E(H^{*}_{0})$. Then
by Remark 3.8,

$\mu(v_{5}v_{2})+\mu(v_{5}v_{6})+\mu(v_{2}v_{6})+d_{H^{*}}(v_{1})\leq D-2.$

Thus,

$\mu(v_{5}v_{2})+\mu(v_{5}v_{6})\leq D-2-d_{H^{*}}(v_{1})\leq
D-2-(2s^{*}-4D+4).$ (3)

Observe that $d_{H^{*}_{0}}(v_{5})\leq 4$ since $v_{5}v_{1}\notin
E(H^{*}_{0})$. Thus, by Claim 3.9(4), we have that
$d_{H^{*}}(v_{5})\geq\frac{4}{3}(s^{*}-2D+2)$.

Since $\mu(v_{5}v_{2})+\mu(v_{5}v_{6})\leq
D-2-(2s^{*}-4D+4)<\frac{4}{3}(s^{*}-2D+2)<d_{H^{*}}(v_{5})$, we have that
$N_{H^{*}_{0}}(v_{5})\cap\\{v_{3},v_{4}\\}\neq\emptyset$. Without loss of
generality, say $v_{5}v_{4}\in E(H^{*}_{0})$. Then by Remark 3.8, we have that

$\mu(v_{3}v_{2})+\mu(v_{3}v_{6})+\mu(v_{2}v_{6})+d_{H^{*}}(v_{1})\leq D-2.$

Thus,

$\mu(v_{3}v_{2})+\mu(v_{3}v_{6})+\mu(v_{2}v_{6})\leq D-2-(2s^{*}-4D+4).$ (4)

If $v_{3}v_{5}\notin E(H^{*}_{0})$, then by inequalities (3) and (4)

$\displaystyle d_{H^{*}}(v_{4})+d_{H^{*}}(v_{1})+2(5D-2s^{*}-6)$
$\displaystyle=d_{H^{*}}(v_{4})+d_{H^{*}}(v_{1})+2(D-2-(2s^{*}-4D+4))$
$\displaystyle\geq
d_{H^{*}}(v_{4})+d_{H^{*}}(v_{1})+\mu(v_{2}v_{3})+\mu(v_{3}v_{6})+\mu(v_{2}v_{6})+\mu(v_{5}v_{2})+\mu(v_{5}v_{6})$
$\displaystyle=s^{*}>{\frac{5}{2}D-60}.$

Thus, $d_{H^{*}}(v_{4})>D$ or $d_{H^{*}}(v_{1})>D$ since
$2(5D-2s^{*}-6)<2(5D-2(\frac{5}{2}D-60)-6)=228$. This is a contradiction.
Therefore, $\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{3}\\}\subseteq E(H^{*}_{0})$.

Since $d_{H^{*}_{0}}(v_{1})=2$ and
$\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{3}\\}\subseteq E(H^{*}_{0})$, by Remark 3.8,
we have that $\mu(v_{2}v_{6})+d_{H^{*}}(v_{1})\leq D-2$ which implies that
$\mu(v_{2}v_{6})\leq D-2-d_{H^{*}}(v_{1})\leq 5D-2s^{*}-6$.

By Claim 3.9(1) with $v_{1}v_{2}\in E(H^{*}_{0})$, we have that

$\displaystyle\mu(v_{2}v_{3})+\mu(v_{2}v_{4})+\mu(v_{2}v_{5})$
$\displaystyle\geq s^{*}-D+2-d_{H^{*}}(v_{1})-\mu(v_{2}v_{6})$
$\displaystyle\geq s^{*}-D+2-(D-2)$ $\displaystyle>\frac{D}{2}-60.$

Then, without loss of generality, say

$\mu(v_{2}v_{3})\geq\frac{\frac{D}{2}-60}{3}>\frac{D}{7}.$

It implies that

$\mu(v_{1}v_{6})+\mu(v_{1}v_{2})+\mu(v_{2}v_{3})=d_{H^{*}}(v_{1})+\mu(v_{2}v_{3})\geq
2s^{*}-4D+4+\frac{D}{7}>D-2,$

which leads to a contradiction since all of these edges are not adjacent with
$v_{4}v_{5}$ in $H^{*}$. Therefore, each vertex in $H^{*}_{0}$ has degree at
least 3. ∎

######  Claim 3.13.

[3] If $v,w,x,y\in T^{*}$ are distinct vertices and $vw,xy\in E(H^{*})$, then
$\mu(vx)+\mu(vy)+\mu(wx)+\mu(wy)\geq s^{*}-2D+2$.

###### Proof.

Let $E_{1}:=\\{e\in
E(H^{*}):e\text{~{}does~{}not~{}share~{}any~{}endpoint~{}with}~{}vw\\}$,
$E_{2}:=\\{e\in
E(H^{*}):e\text{~{}does~{}not~{}share~{}any~{}endpoint~{}with}~{}xy\\}$ and
$E_{3}:=E(H^{*})\setminus(E_{1}\cup E_{2})$. Note that for each edge $e\in
E_{3}$, $e$ has one endpoint in $\\{v,w\\}$ and the other endpoint in
$\\{x,y\\}$. Thus, $|E_{3}|=\mu(wx)+\mu(vx)+\mu(wy)+\mu(vy)$. Since
$v,w,x,y\in T^{*}$ are distinct vertices and $vw,xy\in E(H^{*})$, by Remark
3.8, we have that $|E_{1}|\leq D-2$ and $|E_{2}|\leq D-2$. Therefore,
$|E_{3}|=|E(H^{*})\setminus(E_{1}\cup
E_{2})|\geq|E(H^{*})|-|E_{1}|-|E_{2}|\geq s^{*}-2(D-2)>s^{*}-2D+2$. ∎

######  Remark 3.14.

Note that if there are distinct vertices $v,w,x,y\in T^{*}$ with $vw,xy\in
E(H^{*})$, and $vx,vy,wx\notin E(H^{*})$, then by Claim 3.13, we have that
$\mu(wy)\geq s^{*}-2D+2>\frac{5}{2}D-60-2D+2>\frac{D}{2}-60$. This helps us to
show that the degree of $w$ in $H^{*}$ is large.

######  Claim 3.15.

$\bar{H^{*}_{0}}$ is triangle free.

###### Proof.

Observe that $\bar{H^{*}_{0}}$ contains at most two triangles since each
vertex of $H^{*}_{0}$ has degree at least three. Suppose that
$\bar{H^{*}_{0}}$ contains a triangle. Then it suffices to consider the
following three cases.

Case 1 $\bar{H^{*}_{0}}$ consists of two disjoint triangles.

Let $H_{1}:=H^{*}_{0}$, as shown in Figure 3(1). By Claim 3.9(1), for each
edge $vw\in E(H_{1})$, we have that $d_{H^{*}}(v)+d_{H^{*}}(w)-\mu(vw)\geq
s^{*}-(D-2)$. Summing over all $9$ edges of $H_{1}$ gives

$\sum_{vw\in E(H_{1})}(d_{H^{*}}(v)+d_{H^{*}}(w)-\mu(vw))\geq\sum_{vw\in
E(H_{1})}(s^{*}-(D-2)).$ ($\mathcal{A}$)

It is straightforward to check that each edge of $H^{*}$ is counted exactly 5
times. Thus, the inequality can be rewritten as

$5s^{*}\geq 9(s^{*}-(D-2)),$

which simplifies to $s^{*}\leq\frac{9}{4}(D-2)<\frac{5}{2}D-60$, a
contradiction.

3$v_{1}$3$v_{2}$$v_{3}$3$v_{4}$3$v_{5}$3$v_{6}$3(1)

4$v_{1}$5$v_{2}$$v_{3}$4$v_{4}$4$v_{5}$4$v_{6}$3(2)

3$v_{1}$4$v_{2}$$v_{3}$3$v_{4}$5$v_{5}$4$v_{6}$3(3)

3$v_{1}$5$v_{2}$$v_{3}$3$v_{4}$5$v_{5}$5$v_{6}$3(4)

Figure 3: The graphs $H^{*}_{0}$ and $H_{1}$ in the proof of Claim 3.15

Case 2 $\bar{H^{*}_{0}}$ consists of a disjoint union of a triangle and a path
of length 2.

Let $H_{1}$ be the multigraph obtained from $H^{*}_{0}$ by adding edges, as
shown in Figure 3(2). The inequality ($\mathcal{A}$), now, can be rewritten as

$7s^{*}\geq 12(s^{*}-(D-2)),$

since $H_{1}$ has 12 edges and each edge of $H^{*}$ is counted at most 7
times. Therefore, $s^{*}\leq\frac{12}{5}(D-2)<\frac{5}{2}D-60$, a
contradiction.

Case 3 $\bar{H^{*}_{0}}$ consists of a disjoint union of a triangle and a path
of length 1 or $\bar{H^{*}_{0}}$ consists of a triangle.

It suffices to consider that $H^{*}_{0}$ is as shown in Figure 3(3) or 3(4).
Note that $d_{H^{*}_{0}}(v_{1})=d_{H^{*}_{0}}(v_{3})=d_{H^{*}_{0}}(v_{6})=3$.
Then, by Claim 3.9(4), $d_{H^{*}}(v_{i})\geq\frac{3}{2}(s^{*}-2D+2)$ for each
$i\in\\{1,3,6\\}$.

Since for $\\{i,j,k\\}=\\{1,3,6\\}$ each edge in
$\\{v_{i}v_{2},v_{i}v_{4},v_{j}v_{2},v_{j}v_{4},v_{2}v_{4}\\}$ is disjoint
from $v_{5}v_{k}$, by Remark 3.8, we have that

$\displaystyle\mu(v_{i}v_{2})+\mu(v_{i}v_{4})+\mu(v_{j}v_{2})+\mu(v_{j}v_{4})+\mu(v_{2}v_{4})\leq
D-2.$

Observe that, by Claim 3.9(3), $\mu(v_{i}v_{2})+\mu(v_{i}v_{4})\geq
s^{*}-2D+2$ and $\mu(v_{j}v_{2})+\mu(v_{j}v_{4})\geq s^{*}-2D+2$. Thus, by
inequality (3.2) above, we have that

$\displaystyle\mu(v_{i}v_{2})+\mu(v_{i}v_{4})$ $\displaystyle\leq
D-2-(\mu(v_{j}v_{2})+\mu(v_{j}v_{4}))$ $\displaystyle\leq
D-2-(s^{*}-2D+2)=3D-s^{*}-4,\mbox{ and }$ $\displaystyle\mu(v_{2}v_{4})$
$\displaystyle\leq
D-2-(\mu(v_{i}v_{2})+\mu(v_{i}v_{4})+\mu(v_{j}v_{2})+\mu(v_{j}v_{4}))$
$\displaystyle\leq D-2-2(s^{*}-2D+2)=5D-2s^{*}-6.$

By the same argument, for $\\{i,j,k\\}=\\{1,3,6\\}$, since each edge in
$\\{v_{i}v_{4},v_{i}v_{5},v_{k}v_{4},v_{k}v_{5},v_{4}v_{5}\\}$ is disjoint
from $v_{2}v_{j}$ and each edge in
$\\{v_{i}v_{2},v_{i}v_{5},v_{j}v_{2},v_{j}v_{5},v_{2}v_{5}\\}$ is disjoint
from $v_{4}v_{k}$, we have that

$\displaystyle\mu(v_{i}v_{4})+\mu(v_{i}v_{5})+\mu(v_{k}v_{4})+\mu(v_{k}v_{5})+\mu(v_{4}v_{5})$
$\displaystyle\leq$ $\displaystyle D-2,\mbox{ and }$
$\displaystyle\mu(v_{i}v_{2})+\mu(v_{i}v_{5})+\mu(v_{j}v_{2})+\mu(v_{j}v_{5})+\mu(v_{2}v_{5})$
$\displaystyle\leq$ $\displaystyle D-2.$

Again, from Claim 3.9(3), we have the following inequalities which are the
same type as (3.2).

$\displaystyle s^{*}-2D+2\leq\mu(v_{i}v_{4})+\mu(v_{i}v_{5})$
$\displaystyle\leq$ $\displaystyle D-2-(s^{*}-2D+2)=3D-s^{*}-4,$
$\displaystyle\mu(v_{4}v_{5})$ $\displaystyle\leq$ $\displaystyle
D-2-2(s^{*}-2D+2)=5D-2s^{*}-6,$ $\displaystyle
s^{*}-2D+2\leq\mu(v_{i}v_{2})+\mu(v_{i}v_{5})$ $\displaystyle\leq$
$\displaystyle D-2-(s^{*}-2D+2)=3D-s^{*}-4,$ $\displaystyle\mu(v_{2}v_{5})$
$\displaystyle\leq$ $\displaystyle D-2-2(s^{*}-2D+2)=5D-2s^{*}-6.$

Next we claim that $\mu(v_{i}v_{p})\geq\frac{3}{2}s^{*}-\frac{7}{2}D+3$ for
each $p\in\\{2,4,5\\}$. Suppose not; then for each
$q\in\\{2,4,5\\}\setminus\\{p\\}$, by claim 3.9(3), we have that

$\mu(v_{i}v_{q})\geq s^{*}-2D+2-\mu(v_{i}v_{p})\geq
s^{*}-2D+2-\left(\frac{3}{2}s^{*}-\frac{7}{2}D+3\right)=\frac{3}{2}D-\frac{s^{*}}{2}-1$

which implies that for $\\{q,\ell\\}=\\{2,4,5\\}\setminus\\{p\\}$, we have hat

$\mu(v_{i}v_{q})+\mu(v_{i}v_{\ell})\geq
2\left(\frac{3}{2}D-\frac{s^{*}}{2}-1\right)=3D-s^{*}-2>3D-s^{*}-4.$

This is a contradiction to inequality (3.2). Hence,
$\mu(v_{i}v_{p})\geq\frac{3}{2}s^{*}-\frac{7}{2}D+3$ for each
$p\in\\{2,4,5\\}$.

Therefore, by the symmetry of $i,j,k$, for each $s\in\\{1,3,6\\}$ and
$t\in\\{2,4,5\\}$, we have that

$\mu(v_{s}v_{t})\geq\frac{3}{2}s^{*}-\frac{7}{2}D+3.$

From the upper bounds on $\mu(v_{2}v_{5}),\ \mu(v_{4}v_{5}),$ and
$\mu(v_{2}v_{4})$ in inequality (3.2), we have that

$\mu(v_{2}v_{5})+\mu(v_{4}v_{5})+\mu(v_{2}v_{4})\leq
3\left(D-2-2(s^{*}-2D+2)\right)=3(5D-2s^{*}-6).$

So,

$d_{H^{*}}(v_{1})+d_{H^{*}}(v_{3})+d_{H^{*}}(v_{6})\geq
s^{*}-3(5D-2s^{*}-6)=7s^{*}-15D+18.$

Then there are integers $s\in\\{1,3,6\\}$ and $t\in\\{2,4,5\\}$ such that

$d_{H^{*}}(v_{s})\geq\frac{1}{3}(7s^{*}-15D+18)\mbox{ and
}\mu(v_{s}v_{t})\geq\frac{1}{9}(7s^{*}-15D+18).$

Then, for each $r\in\\{2,4,5\\}\setminus\\{t\\}$, we have that

$\mu(v_{s}v_{t})+\mu(v_{s}v_{r})\geq\frac{1}{9}(7s^{*}-15D+18)+\frac{3}{2}s^{*}-\frac{7}{2}D+3>3D-s^{*}-4.$

This is a contradiction to inequality (3.2).

Therefore, $\bar{H^{*}_{0}}$ is triangle free. ∎

Now, we prove that $H^{*}_{0}$ is actually a complete graph.

######  Claim 3.16.

$H^{*}_{0}$ is a complete graph.

###### Proof.

Note that it is impossible for $\bar{H^{*}_{0}}$ to contain a star $K_{1,t}$
where $t\geq 3$ since each vertex of $H^{*}_{0}$ has degree at least three. We
start the proof by asserting that there is no paths and cycles of length at
least 4 in $\bar{H^{*}_{0}}$. Suppose, to the contrary, that there is a path
of length 4 in $\bar{H^{*}_{0}}$. Without loss of generality, let
$v_{1}v_{6}v_{5}v_{4}v_{3}$ be a path of length 4 contained in
$\bar{H^{*}_{0}}$. Then $v_{2}v_{5}\in E(H^{*}_{0})$ by Claim 3.12. Consider
the edges $v_{1}v_{5},v_{6}v_{4}$ and $v_{3}v_{5},v_{6}v_{4}$. Then by Claim
3.13, we have that

$\mu(v_{1}v_{4})\geq s^{*}-2D+2\mbox{ and }\mu(v_{3}v_{6})\geq s^{*}-2D+2.$

So, by Claim 3.9(3), we have that $d_{H^{*}}(v_{1}),$
$d_{H^{*}}(v_{4}),d_{H^{*}}(v_{3}),$ $d_{H^{*}}(v_{6})\geq
2(s^{*}-2D+2)=2s^{*}-4D+4$. Then

$d_{H^{*}}(v_{2})+d_{H^{*}}(v_{5})\leq
2s^{*}-4(2s^{*}-4D+4)=16D-6s^{*}-16<s^{*}-D+2,$

contradicting to Claim 3.9(1) since $v_{2}v_{5}\in E(H^{*}_{0})$. It also
implies that there is no paths and cycles of length at least 5. Thus, to prove
the assertion, it is sufficient to show that $\bar{H}^{*}_{0}$ does not
contain $C_{4}$ as a subgraph. Suppose, to the contrary, that
$v_{3}v_{4}v_{5}v_{6}v_{3}$ is a cycle of length 4 contained in
$\bar{H}^{*}_{0}$. Then by Claim 3.13 with edges $v_{3}v_{5}$ and $v_{4}v_{6}$
contained in $H^{*}$, we have the following contradiction.

$0=\mu(v_{3}v_{4})+\mu(v_{4}v_{5})+\mu(v_{5}v_{6})+\mu(v_{3}v_{6})\geq
s^{*}-2D+2>0.$

Thus, the assertion holds. Therefore, by Claim 3.15 and what we have proved
above, there is no cycles contained in $\bar{H}^{*}_{0}$ and the paths
contained in $\bar{H}^{*}_{0}$ is of length at most 3.

Now, we will show that there is no path of length at least 1 in
$\bar{H}^{*}_{0}$. Suppose, to the contrary, that there is a path of length at
least 1 in $\bar{H}^{*}_{0}$. Then, according to the length of paths and the
number of vertex disjoint paths contained in $\bar{H}^{*}_{0}$, all the
possible cases needed to consider are that $\bar{H}^{*}_{0}$ consists of

  1. (1)

a disjoint union of a path of length 3 and a path of length 1,

  2. (2)

a path of length 3,

  3. (3)

2 vertex disjoint paths of length 2,

  4. (4)

a disjoint union of a path of length 2 and a path of length 1,

  5. (5)

a path of length 2,

  6. (6)

3 vertex disjoint paths of length 1,

  7. (7)

2 vertex disjoint paths of length 1, or

  8. (8)

a path of length 1.

6$v_{1}$6$v_{2}$$v_{3}$5$v_{4}$6$v_{5}$6$v_{6}$5$\eta=10,\gamma=17$(1)

7$v_{1}$7$v_{2}$$v_{3}$7$v_{4}$8$v_{5}$8$v_{6}$7$\eta=13,\gamma=22$(2)

4$v_{1}$4$v_{2}$$v_{3}$4$v_{4}$4$v_{5}$4$v_{6}$4$\eta=7,\gamma=12$(3)

8$v_{1}$7$v_{2}$$v_{3}$8$v_{4}$8$v_{5}$6$v_{6}$7$\eta=13,\gamma=22$(4)

9$v_{1}$7$v_{2}$$v_{3}$7$v_{4}$7$v_{5}$7$v_{6}$7$\eta=13,\gamma=22$(5)

8$v_{1}$8$v_{2}$$v_{3}$8$v_{4}$8$v_{5}$8$v_{6}$8$\eta=14,\gamma=24$(6)

6$v_{1}$5$v_{2}$$v_{3}$5$v_{4}$6$v_{5}$6$v_{6}$6$\eta=10,\gamma=17$(7)

7$v_{1}$7$v_{2}$$v_{3}$7$v_{4}$8$v_{5}$8$v_{6}$7$\eta=13,\gamma=22$(8)

Figure 4: The multigraph $H_{1}$ defined for cases (1)-(8) in the proof of
Claim 3.16 and the degree of each vertex in $H_{1}$ is listed.

Here, we prove that none of the cases happens by hiring the same argument as
that used in the proof of Case 1 in Claim 3.15. For each $i\in[8]$, let
$H_{1}$ be a multigraph obtained from $H^{*}_{0}$ by adding edges, as shown in
Figure 4(i). Furthermore, for each edge $vw\in E(H^{*})$, let $c(vw)$ be the
number of times that $vw$ is counted while summing over all the edges of
$H_{1}$ in the left side of inequality ($\mathcal{A}$). Then,
$c(vw)=d_{H_{1}}(v)+d_{H_{1}}(w)-\mu_{H_{1}}(vw)$. Let

$\gamma:=|E(H_{1})|~{}\text{and}~{}\eta:=\max_{vw\in E(H^{*})}c(vw),$

as shown in Figure 4 for each case. Then, inequality ($\mathcal{A}$), now, can
be rewritten as

$\eta s^{*}\geq\gamma(s^{*}-(D-2)),$

which can be simplified to
$s^{*}\leq\frac{\gamma}{\gamma-\eta}(D-2)<\frac{5}{2}D-60$, a contradiction.

Therefore, $H^{*}_{0}$ is a complete graph. ∎

###  3.3 Final step of the Proof of Theorem 1.6

In this subsection, we complete the proof of Theorem 1.6. From the previous
subsection, we know that $H^{*}_{0}$ is a complete graph. We first show that
the multigraph $H^{*}$ is almost balanced. That is, in Claim 3.17, we show
that each vertex $v$ in $H^{*}$ has $\frac{5}{6}D-c_{1}\leq
d_{H^{*}}(v)\leq\frac{5}{6}D+c_{1}^{\prime}$ and, in Claim 3.20, we show that
the multiplicity of each edge $uv$ in $H^{*}$ satisfies
$\mu(uv)\geq\frac{D}{6}-c_{2}$ where $c_{1}$, $c_{1}^{\prime}$ and $c_{2}$ are
small enough compared to $D$. Next, by introducing new terms, we compute the
size of $S\setminus S^{*}$ in Claim 3.21–Claim 3.23. Finally, we finish the
proof of Theorem 1.6 at the end of this subsection.

First, we show the following claim.

######  Claim 3.17.

Let $v\in T^{*}$. Then $\frac{25D-9s^{*}-50}{3}\geq
d_{H^{*}}(v)\geq\frac{3s^{*}-5D+10}{3}$.

###### Proof.

Since $H^{*}_{0}$ is a complete graph, by Claim 3.9(3) for distinct
$i,j\in[6]$,

$d_{H^{*}}(v_{i})+d_{H^{*}}(v_{j})-\mu(v_{i}v_{j})\geq s^{*}-D+2.$

Then

$\displaystyle\left(\sum_{i\in[6]\setminus\\{j\\}}d_{H^{*}}(v_{i})\right)+5d_{H^{*}}(v_{j})-\sum_{i\in[6]\setminus\\{j\\}}\mu(v_{i}v_{j})$
$\displaystyle=\left(\sum_{v\in T^{*}}d_{H^{*}}(v)\right)+3d_{H^{*}}(v_{j})$
$\displaystyle\geq 5(s^{*}-D+2).$

Thus, for each vertex $v_{j}$ in $H^{*}$,

$d_{H^{*}}(v_{j})\geq\frac{5(s^{*}-D+2)-2s^{*}}{3}=\frac{3s^{*}-5D+10}{3}.$

Therefore, since $|T^{*}|=6$, we have that

$d_{H^{*}}(v)=2s^{*}-\sum_{u\in T^{*}\setminus\\{v\\}}d_{H^{*}}(u)\leq
2s^{*}-5\frac{3s^{*}-5D+10}{3}\\\ =\frac{25D-9s^{*}-50}{3}.$

∎

Note that Claim 3.17 implies that for each vertex $v$ in $H^{*}$, we have that
$\frac{5}{6}D-57\leq d_{H^{*}}(v)\leq\frac{5}{6}D+164$.

$R^{*}$$W$$S$$S^{*}$$T^{*}$$U$ Figure 5: The relations between sets $S$,
$R^{*}$ and $T^{*}$.

Recall that $V(G)=V(G^{*})=R^{*}\cup S^{*}\cup T^{*}$. Let $W:=S\cap R^{*}$
and $U:=S\cap T^{*}$, as shown in Figure 5. Then $S=W\cup S^{*}\cup U$ and
$W\cap S^{*}=U\cap S^{*}=\emptyset$. We establish a claim which tells us the
adjacency between vertices in $W\cup U$ and $T^{*}$ in the graph $G$.

######  Claim 3.18.

  * (1)

Let $v\in U$. Then $2\leq|N_{G}(v)\cap T^{*}|\leq 5$.

  * (2)

Let $v\in W$. Then $2\leq|N_{G}(v)\cap T^{*}|\leq 6$.

###### Proof.

By Claim 3.11.1, if $v\in S\setminus S^{*}$ and $|T^{*}|=6$, then
$|N_{G}(v)\cap T^{*}|\geq 2$. Since $S\setminus S^{*}=W\cup U$ by the
definition of $W$ and $U$, we have that (1) and (2) hold. ∎

Let $U_{i}:=\\{u\in U:|N_{G}(u)\cap T^{*}|=i\\}$ and $\alpha_{i}:=|U_{i}|$
where $i\in[5]$. Observe that by Claim 3.18, $\alpha_{1}=0$. Let
$W_{i}:=\\{u\in W:|N_{G}(u)\cap T^{*}|=i+1\\}$ and $\beta_{i}:=|W_{i}|$ where
$i\in[5]$. Then

$|S\setminus S^{*}|=\sum^{5}_{i=1}(\alpha_{i}+\beta_{i})>\frac{5}{2}D-s^{*}.$

Next, we start to count the number of vertices in $S\setminus S^{*}$. We use
double counting strategy. For this, we define $D_{i,j}$, $S_{i,j}$, and
$V_{i,j}$ as follows.

######  Definition 3.19.

Let $T^{*}=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$.

  1. (1)

For $1\leq i<j\leq 6$, let

$D_{i,j}:=\\{v\in S^{*}:N_{G^{*}}(v)\cap\\{v_{i},v_{j}\\}=\emptyset\\}$

and let $|D_{i,j}|=d_{i,j}$. Note that each vertex in $D_{i,j}$ corresponding
to an edge in $H^{*}$ that are incident to neither $v_{i}$ nor $v_{j}$. And
note that $d_{i,j}\leq D-2$ by Claim 3.9 (1), since $H_{0}^{*}$ is a complete
graph.

  2. (2)

For $1\leq i<j\leq 6$, let

$S_{i,j}:=\\{v\in
S\setminus(S^{*}\cup\\{v_{i},v_{j}\\}):~{}N_{G}(v)\cap\\{v_{i},v_{j}\\}=\emptyset\\}$

and let $s_{i,j}:=|S_{i,j}|$. Note that $S_{i,j}$ is the set of vertices in
$S\setminus(S^{*}\cup\\{v_{i},v_{j}\\})$ that are adjacent to neither $v_{i}$
nor $v_{j}$.

  3. (3)

For each edge $v_{i}v_{j}\in E(H^{*}_{0})$, let $V_{i,j}$ be the set of
vertices in $S^{*}$ that correspond to edges between $v_{i}$ and $v_{j}$.
Then, by Construction 3.6, we have that $|V_{i,j}|=\mu(v_{i}v_{j})$.

As outlined above, we will show that $H^{*}$ is almost balanced. By applying
Claim 3.17, we show that for every distinct $i,j\in[6]$,
$|V_{i,j}|=\mu(v_{i}v_{j})\geq\frac{D}{6}-2000$. This is formalized in the
following claim.

######  Claim 3.20.

For every distinct $i,j\in[6]$,
$|V_{i,j}|=\mu(v_{i}v_{j})\geq\frac{87s^{*}-217D+374}{3}$. Furthermore,
$|V_{i,j}|>\frac{D}{6}-2000$.

###### Proof.

Suppose that $\mu(v_{i}v_{j})\leq\frac{87s^{*}-217D+373}{3}$ for some
$i,j\in[6]$. Then, by the Pigeonhole principle, there exists
$k\in[6]\setminus\\{i,j\\}$ such that
$\mu(v_{i}v_{k})\geq\frac{d_{H^{*}}(v_{i})-\frac{87s^{*}-217D+373}{3}}{4}$.
Then by Claim 3.17 and Remark 3.1, we have that

$\displaystyle d_{H^{*}}(v_{i})+d_{H^{*}}(v_{k})-\mu(v_{i}v_{k})$
$\displaystyle\leq\frac{3}{4}d_{H^{*}}(v_{i})+d_{H^{*}}(v_{k})+\frac{87s^{*}-217D+373}{12}$
$\displaystyle\leq\frac{7}{4}\left(\frac{25D-9s^{*}-50}{3}\right)+\frac{87s^{*}-217D+373}{12}$
$\displaystyle\leq\frac{175D-63s^{*}-350+87s^{*}-217D+373}{12}$
$\displaystyle\leq\frac{24s^{*}-42D+23}{12}$ $\displaystyle<s^{*}-D+2,$

a contradiction. Thus, for every distinct $i,j\in[6]$, we have that
$|V_{i,j}|=\mu(v_{i}v_{j})\geq\frac{87s^{*}-217D+374}{3}$, and
$|V_{i,j}|\geq\frac{0.5D-87\times 60+374}{3}>\frac{D}{6}-2000$, since
$s^{*}>\frac{5}{2}D-60$. ∎

######  Claim 3.21.

For $1\leq i<j\leq 6$, $d_{i,j}\geq 6s^{*}-14D+28$.

###### Proof.

Note that $\sum_{1\leq i<j\leq 6}d_{i,j}=6|E(H^{*})|=6s^{*}$. Since
$d_{i^{\prime},j^{\prime}}\leq D-2$ for each $1\leq i^{\prime}<j^{\prime}\leq
6$, we have that

$d_{i,j}=6s^{*}-\sum_{\\{i^{\prime},j^{\prime}\\}\neq\\{i,j\\}}d_{i^{\prime},j^{\prime}}\geq
6s^{*}-14(D-2)=6s^{*}-14D+28.$

∎

Note that Claim 3.21 implies that for each $1\leq i<j\leq 6$, we have
$d_{i,j}\geq 6s^{*}-14D+28>D-332$, since $s^{*}>\frac{5}{2}D-60$.

######  Claim 3.22.

For each vertex $v\in V_{i,j}$, let $R_{v}:=\\{w\in R^{*}\cap
N_{G^{*}}(v):N_{G^{*}}(w)\cap D_{i,j}\neq\emptyset\\}$. Then we have that
$|R_{v}|\geq d_{i,j}$.

###### Proof.

Since $v\in S^{*}$ and $S^{*}$ induces a complete subgraph of ${(G^{*})}^{2}$,
for each $u\in D_{i,j}$, there is a vertex $w\in R^{*}$ such that $vw,wu\in
E(G^{*})$. Recall that for each vertex $w\in R^{*}$, by Remark 3.3, we have
that $|N_{G^{*}}(w)\cap S^{*}|\leq 2$. Thus, $|R_{v}|\geq d_{i,j}$ as
$\\{v\\}\cup D_{i,j}\subseteq S^{*}$. ∎

Next, we show a very important claim which plays central role in the proof. We
give an upper bound on the size of $S_{i,j}$ as follows. Recall that $S_{i,j}$
is the set of vertices in $S\setminus(S^{*}\cup\\{v_{i},v_{j}\\})$ that are
adjacent to neither $v_{i}$ nor $v_{j}$, and $s_{i,j}=|S_{i,j}|$. The outline
of the proof Claim 3.23 is as follows. We will show that $|S_{i,j}|$ is not
too large. If $|S_{i,j}|$ is large enough, then there is a subset $Z$ of
$S_{i,j}$ of size exactly $D-1-d_{i,j}$. Then each vertex in $V_{i,j}$ should
adjacent in $G^{2}$ to each vertex in $Z$. Then we show that there is some
vertex $v$ in $V_{i,j}$ such that for each $z\in Z$, there is a vertex
$w_{z}\in N_{G}(v)\setminus(R_{v}\cup\\{v_{i},v_{j}\\})$ with
$vw_{z},zw_{z}\in E(G)$ where for distinct $z_{1},z_{2}\in Z$, we have that
$w_{z_{1}}\neq w_{z_{2}}$. Then, along with $R_{v}$ and $v_{i},v_{j}$, we have
that the degree of $v$ in $G$ is at least $d_{i,j}+2+D-1-d_{i,j}>D$, a
contradiction.

######  Claim 3.23.

For $1\leq i<j\leq 6$, we have that $s_{i,j}\leq D-2-d_{i,j}$.

###### Proof.

Suppose that $s_{i,j}>D-2-d_{i,j}$ for some $i,j$. Let $Z\subseteq S_{i,j}$
with $|Z|=D-1-d_{i,j}$, then by Claim 3.21, we have that

$|Z|=D-1-d_{i,j}\leq D-1-(6s^{*}-14D+28)\leq
6\left(\frac{5}{2}D-s^{*}\right)-29<331.$

Let

$V_{0}=\\{u\in V_{i,j}:N_{G}(u)\cap Z\neq\emptyset\\}.$

Since $Z\subseteq S_{i,j}$, by Remark 3.3, we have that

$|V_{0}|\leq 2Z<2\times 331.$ (5)

Then for each vertex in $v\in V_{i,j}\setminus V_{0}$ and each vertex $u\in
Z$, there should be a vertex $w\in R^{*}\cup T^{*}$ such that $vw,uw\in E(G)$.
Since for each vertex $v$ in $V_{i,j}$, $N_{G}(v)\cap T^{*}=\\{v_{i},v_{j}\\}$
and each vertex in $S_{i,j}$ is adjacent to neither $v_{i}$ nor $v_{j}$, we
have that $w\in R^{*}$. Additionally, recall that for $v\in V_{i,j}$ each
vertex in $R_{v}$ has one neighbor $v$ and another neighbor in
$D_{i,j}\subseteq S$. Thus, by Remark 3.3 with $w\in R^{*}$, we have that
$w\in R^{*}\setminus R_{v}$. For any pair of vertices $x,y\in Z$, let

$W_{x,y}=\\{w\in V(G):wx,wy\in
E(G)~{}\text{and}~{}N_{G}(w)\cap(V_{i,j}\setminus V_{0})\neq\emptyset\\}.$

For any $w\in W_{x,y}$, we have that $|N_{G}(w)\cap(V_{i,j}\setminus
V_{0})|\leq 2$ by Remark 3.3 with $w\in R^{*}$ and $V_{i,j}\subseteq S^{*}$.

Next we claim that $|W_{x,y}|\leq 5$. Suppose that $|W_{x,y}|\geq 6$. Let
$B_{x,y}:=N_{G}(W_{x,y})\cap(V_{i,j}\setminus V_{0})$. Then $|B_{x,y}|\geq 3$.
Otherwise the subgraph of $G$ induced by $B_{x,y}\cup W_{x,y}\cup\\{x,y\\}$ is
not 2-degenerate. But $|B_{x,y}|\geq 3$ implies that the subgraph of $G$
induced by $\\{x,y,v_{i},v_{j}\\}\cup B_{x,y}\cup W_{x,y}$ is not 2-degenerate
since every vertex in the induced subgraph has degree at least 3. Thus,
$|W_{x,y}|\leq 5$ for any pair of vertices in $Z$. Hence,

$\left|\bigcup_{x,y\in Z}W_{x,y}\right|\leq\sum_{x,y\in Z}|W_{x,y}|\leq
5\times{{|Z|}\choose 2}<5\times{331\choose 2}.$

Figure 6:  An example for adjacency in $G$ between vertices in $V_{i,j}$ and
$Z$

Let

$Q=\\{v\in V_{i,j}\setminus V_{0}:\text{there is a vertex $w\in
N_{G}(v)\setminus\\{v_{i},v_{j}\\}$ such that $|N_{G}(w)\cap Z|\geq 2$}\\}.$

Thus, by Remark 3.3,

$|Q|\leq 2\left|\bigcup_{x,y\in Z}W_{x,y}\right|<10\times{331\choose 2}.$ (6)

Now, we consider the subset $V_{i,j}\setminus(Q\cup V_{0})$ (see Figure 6).
Note that $|V_{i,j}|>\frac{D}{6}-2000$ from Claim 3.20 and $D\geq
D_{0}=6\times(331\times 2+10\times{331\choose 2}+2000)$. (Note that this is
the only place where we need large value of $D_{0}$.) So, by the inequalities
(5) and (6) we have that

$|V_{i,j}\setminus(Q\cup V_{0})|\geq|V_{i,j}|-|Q|-|V_{0}|>0.$

Thus the subset $V_{i,j}\setminus(Q\cup V_{0})$ is nonempty. Then for each
vertex $v$ in $V_{i,j}\setminus(Q\cup V_{0})$ and each vertex $x\in Z$, there
is a vertex $w_{v,x}\in R^{*}\setminus R_{v}$ such that $vw_{v,x},xw_{v,x}\in
E(G)$; furthermore, for distinct $x,x^{\prime}\in Z$, we have that
$w_{v,x^{\prime}}\neq w_{v,x}$ by the choice of $v$ in $V_{i,j}\setminus(Q\cup
V_{0})$. Then $d_{G}(v)\geq|R_{v}\cup\\{v_{i},v_{j}\\}|+|Z|=d_{i,j}+2+|Z|>D$,
a contradiction. This completes the proof of Claim 3.23. ∎

Hence, from Claim 3.23, we have the following property.

$\displaystyle\sum_{1\leq i<j\leq 6}s_{i,j}$ $\displaystyle\leq\sum_{1\leq
i<j\leq 6}(D-2-d_{i,j})$ ($\mathcal{D}$) $\displaystyle=15(D-2)-\sum_{1\leq
i<j\leq 6}d_{i,j}$ $\displaystyle=15(D-2)-6|E(H^{*})|$
$\displaystyle=15D-6s^{*}-30$
$\displaystyle=6\left(\frac{5}{2}D-s^{*}\right)-30.$

Note that the inequality ($\mathcal{D}$) is very important in the final step
of the proof. Let $N_{G}[v]:=N_{G}(v)\cup\\{v\\}$. Next, we count how many
times each vertex in $S\setminus S^{*}$ appears on the left side of inequality
($\mathcal{D}$).

######  Counting 3.24.

Fix $i\in\\{1,2,3,4,5\\}$. For each $v\in U_{i}\cup W_{i}$, we have
$|T^{*}\setminus N_{G}[v]|=5-i$, so $v$ is counted ${5-i\choose 2}$ times on
the left side of inequality ($\mathcal{D}$). Thus, we have the following.

  1. (1)

Each $v\in U_{1}\cup W_{1}$ is counted 6 times one the left side of inequality
($\mathcal{D}$).

  2. (2)

Each $v\in U_{2}\cup W_{2}$ is counted 3 times one the left side of inequality
($\mathcal{D}$).

  3. (3)

Each $v\in U_{3}\cup W_{3}$ is counted 1 time one the left side of inequality
($\mathcal{D}$).

  4. (4)

Each $v\in U_{4}\cup W_{4}\cup U_{5}\cup W_{5}$ is counted 0 time one the left
side of inequality ($\mathcal{D}$).

Therefore, from Counting 3.24 we have that

$\sum_{1\leq i<j\leq
6}s_{i,j}=6(\alpha_{1}+\beta_{1})+3(\alpha_{2}+\beta_{2})+\alpha_{3}+\beta_{3}.$

Recall that $|S\setminus S^{*}|=\sum^{5}_{i=1}(\alpha_{i}+\beta_{i})$. Since
$|S\setminus S^{*}|>\frac{5}{2}D-s^{*}$, if we substitute $|S\setminus S^{*}|$
with $\sum^{5}_{i=1}(\alpha_{i}+\beta_{i})$ in inequality ($\mathcal{D}$),
then we have that

$6(\alpha_{1}+\beta_{1})+3(\alpha_{2}+\beta_{2})+\alpha_{3}+\beta_{3}<6\left(\sum_{i\in[5]}(\alpha_{i}+\beta_{i})\right)-30.$

Thus,

$30<3(\alpha_{2}+\beta_{2})+5(\alpha_{3}+\beta_{3})+6\sum_{i\in\\{4,5\\}}(\alpha_{i}+\beta_{i}).$
($\mathcal{E}$)

Let $J$ be the graph obtained from the subgraph of $G$ induced by $(S\setminus
S^{*})\cup T^{*}$ by deleting edges that are not incident with any vertex in
$T^{*}$. Observe that the graph $J$ is defined by inspiration from Counting
3.24.

Recall that $U=S\cap T^{*}$. Let $U^{*}=\\{u^{*}:u\in U\\}$. Then
$|U^{*}|=|U|$. Let $J^{*}$ be the graph obtained from $J$ which is defined as
follows.

$\displaystyle V(J^{*})$ $\displaystyle=W\cup U^{*}\cup T^{*},$ $\displaystyle
E(J^{*})$ $\displaystyle=\\{ab\in E(H):a\in W,b\in T^{*}\\}\cup\\{u^{*}v:uv\in
E(G),u\in U,v\in T^{*}\\}\cup$ $\displaystyle~{}~{}~{}~{}\\{u^{*}u:u\in U\\}.$

Note that for each $v\in W$, $|N_{J^{*}}(v)|=|N_{J}(v)|$ and for each $v\in
U^{*}$, $|N_{J^{*}}(v)|=|N_{J}(v)\cap T^{*}|+1$.

Next, we show that actually $J^{*}$ is a 2-degenerate bipartite graph.
Finally, we use Claim 3.26 to get a contradiction and finish our proof.

$R^{*}$$W$$u$$S$$S^{*}$$T^{*}$$U$$u^{*}$$U^{*}$ Figure 7: An example of
$J^{*}$ when $U\neq\emptyset$.

######  Claim 3.25.

The graph $J^{*}$ is a 2-degenerate bipartite graph.

###### Proof.

Observe that from the definition of the graph $J^{*}$, we have that $J^{*}$ is
a bipartite graph with bipartition $(W\cup U^{*},T^{*})$. Now, we focus on the
proof that $J^{*}$ is 2-degenerate. Observe that if $U=\emptyset$, then by the
definition of $J^{*}$, we have that $J^{*}$ is a subgraph of $J$ which means
that $J^{*}$ is 2-degenerate.

It suffices to consider the case when $U\neq\emptyset$ as shown in Figure 7.
Note that, by the definition of $J^{*}$, for $u\in U$ and $u^{*}\in U^{*}$ in
$J^{*}$, we have that

$\displaystyle N_{J}(u)$ $\displaystyle=(N_{J}(u)\cap W)\cup(N_{J}(u)\cap
T^{*})$ $\displaystyle=(N_{J^{*}}(u)\cap W)\cup(N_{J^{*}}(u^{*})\cap
T^{*})\setminus\\{u\\}$
$\displaystyle=(N_{J^{*}}(u)\setminus\\{u^{*}\\})\cup(N_{J^{*}}(u^{*})\setminus\\{u\\}),$

where
$(N_{J^{*}}(u)\setminus\\{u^{*}\\})\cap(N_{J^{*}}(u^{*})\setminus\\{u\\})=\emptyset$.

Let $\sigma(J)$ be a 2-degeneracy order of $J$ where each vertex has at most
two neighbors later. To obtained a 2-degeneracy order $\sigma(J^{*})$ of
$J^{*}$ from $J$, we proceed as follows. For each $u\in U$, if there is a
neighbor $w$ of $u$ in $W$ which is later than $u$ in $\sigma(J)$, then put
$u^{*}$ directly before $u$ such that $u^{*}$ and $u$ are consecutive,
otherwise, put $u^{*}$ directly after $u$ such that $u$ and $u^{*}$ are
consecutive. We call it the induced order of $J^{*}$, denoted $\sigma(J^{*})$.

Now, we prove that $\sigma(J^{*})$ is a 2-degeneracy order of $J^{*}$. Note
that for both cases, it suffices to check that $u$ and $u^{*}$ have at most
two neighbors later in the order $\sigma(J^{*})$. For the former, since there
is a neighbor $w$ of $u$ in $W$ which is later than $u$ in $\sigma$, by the
above analysis, $u^{*}w\notin E(J^{*})$. Therefore, $u^{*}$ has at most
$1+(2-1)=2$ neighbors later in $\sigma(J^{*})$ while the number of neighbors
of $u$ that are later does not increase. For the latter, all the neighbors of
$u$ that are later than $u$ in $\sigma(J)$ should be in $T^{*}$, then by the
definition of $J^{*}$, such adjacency does not exist in $J^{*}$, therefore,
$u$ has only one neighbor later in $\sigma(J^{*})$ while there are at most 2
neighbors of $u^{*}$ inherited from $u$ later than $u^{*}$ in $\sigma(J^{*})$.

Therefore, $J^{*}$ is a 2-degenerate bipartite graph. ∎

Define

$\displaystyle x$ $\displaystyle:=|\\{u:u\in W\cup U^{*},|N_{J^{*}}(u)\cap
T^{*}|=3\\}|,$ $\displaystyle y$ $\displaystyle:=|\\{u:u\in W\cup
U^{*},|N_{J^{*}}(u)\cap T^{*}|=4\\}|,$ $\displaystyle z$
$\displaystyle:=|\\{u:u\in W\cup U^{*},|N_{J^{*}}(u)\cap T^{*}|\geq 5\\}|.$

Then inequality ($\mathcal{E}$) can be simplified as

$30<3x+5y+6z.$

Since $J^{*}$ is a 2-degenerate bipartite graph, the following holds.

######  Claim 3.26.

  * (1)

$x+y+z\leq 8$. Furthermore, if $x+y+z=8$, then $y=z=0$ and $x=8$.

  * (2)

$y+z\leq 4$. Furthermore, if $y+z=4$, then $z=0$ and $y=4$.

  * (3)

$z\leq 2$.

###### Proof.

Note that $J^{*}$ is a 2-degenerate bipartite graph. Let $\sigma(J^{*})$ be a
2-degeneracy order of $J^{*}$ where each vertex has at most 2 vertices later.
Let $\\{u,v,w\\}$ be the last three vertices in the order $\sigma(J^{*})$.
Then $|E(J^{*}[\\{u,v,w\\}])|\leq 2$.

For $i\in[3]$, let $Q_{i}:=\\{v\in W\cup U^{*}:d_{J^{*}}(v)\geq i+2\\}$. Let
$J_{i}$ be the subgraph of $J^{*}$ induced by $Q_{i}\cup T^{*}$. That is,
$J_{i}:=J^{*}[Q_{i}\cup T^{*}]$. Then $J_{i}$ is 2-degenerate and bipartite.
From the observation $|E(J^{*}[\\{u,v,w\\}])|\leq 2$, we have that for
$i\in[3]$,

$(i+2)|Q_{i}|\leq\sum_{u\in Q_{i}}|N_{J_{i}}(u)\cap T^{*}|=\sum_{u\in
Q_{i}}d_{J_{i}}(u)=|E(J_{i})|\leq 2(|V(J_{i})|-3)+2\leq 2(6+|Q_{i}|-3)+2,$

which simplifies to $|Q_{i}|\leq 8/i$. Therefore, for $i=1$, we have that
$x+y+z\leq 8$; furthermore equality holds only when $x=8$ and $y=z=0$. For
$i=2$, we have that $y+z\leq 4$; furthermore equality holds only when $y=4$
and $z=0$. For $i=3$, we have that $z\leq 2$. ∎

Thus, we have the following system of linear inequalities:

$\left\\{\begin{array}[]{lr}3x+5y+6z>30;&\\\ x+y+z\leq 8;&\\\ y+z\leq 4;&\\\
z\leq 2;\\\ x,y,z\geq 0.\end{array}\right.$

It is straight forward to check that its only integer solutions are

$(4,4,0),(5,2,1),(4,3,1),(5,1,2),(3,2,2),(4,2,2).$

However, none of these solutions satisfies Claim 3.26. It implies that the
graph $J^{*}$ does not exist which leads to a contradiction.

This completes the proof of Theorem 1.6. ∎

##  4 Remark

The following question was asked in [3].

######  Question 4.1.

For each positive integer $k$, what is the minimum value $\alpha_{k}$ such
that there exists a constant $c_{k}$ such that if $G$ is $k$-degenerate with
maximum degree at most $D$, then $\omega(G^{2})\leq\alpha_{k}D+c_{k}$?

If $G$ is $k$-degenerate with $\Delta(G)\leq D$, then $G^{2}$ has degeneracy
at most $(2k-1)D-k^{2}$, so $\alpha_{k}\leq 2k-1$. In particular, for $k=2$,
Cranston and Yu [3] showed that $\alpha_{2}=\frac{5}{2}$. On the other hand,
our result implies that $c_{2}=0$ when $D\geq D_{0}=6\times(331\times
2+10\times{331\choose 2}+2000)$.

## Acknowledgments

Seog-Jin Kim is supported by the National Research Foundation of Korea(NRF)
grant funded by the Korea government(MSIT)(No.NRF-2021R1A2C1005785), and
Xiaopan Lian is supported by National Natural Science Foundation of China (No.
12161141006) and China Scholarship Council(CSC) Grant $\\#$202306200010\.

## References

  * [1] C. Charpentier, 2-distance coloring of not-so-sparse graphs, preprint. Available at: www.labri.fr/perso/charpent/2dcol-not-so-sparse.pdf, (2014)
  * [2] D. W. Cranston, Coloring, List Coloring, and Painting Squares of Graphs (and Other Related Problems), Electron. J. Combin. 30(2) (2023), $\\#$DS25.
  * [3] D.W. Cranston and G. Yu, Cliques in Squares of Graphs with Maximum Average Degree less than 4, arXiv:2305.11763.
  * [4] D.W. Cranston, Bounding Clique Size in Squares of Planar Graphs, arXiv:2308.09585.
  * [5] S. G. Hartke, S. Jahanbekam, and B. Thomas, The chromatic number of the square of subcubic planar graphs, 2016, arXiv:1604.06504.
  * [6] H. Hocquard, S.-J. Kim, and T. Pierron, Coloring squares of graphs with mad constraints. Discrete Appl. Math., 271:64–73, 2019.
  * [7] H.A. Kierstead, D. Yang, and J. Yi, On coloring numbers of graph powers Discrete Math., 343 (2020), no. 6, 111712.
  * [8] S.-J. Kim and B. Park, Coloring the square of graphs whose maximum average degree is less than 4, Discrete Math. 339 (2016), no. 4, 1251–1260.
  * [9] C. Thomassen, The square of a planar cubic graph is 7-colorable. J. Combin. Theory Ser. B 128 (2018), 192–218.
  * [10] G. Wegner, Graphs with given diameter and a colouring problem, preprint, University of Dortmund (1977).

##  5 Appendix (The Proof of Theorem 2.5)

In this appendix, we present the proof Theorem 2.5. We shall emphasize here
that the proof is exactly that of Theorem 5 in [3]. Theorem 2.5 explains how
to obtain $(G^{*},S^{*},\sigma^{*})$ from $(G,S,\sigma)$ such that
$|S\setminus S^{*}|\leq 60$.

######  Theorem 2.5.

(Theorem 5, [3]) For every positive integer $D\geq 1732$, if a 2-degenerate
graph $G$ with $\Delta(G)\leq D$ satisfies that
$\omega(G^{2})=f(D)>\frac{5}{2}D$, then there is a subgraph $G^{*}$ of $G$
which is nice w.r.t. a clique $S^{*}$ in ${(G^{*})}^{2}$ and $|S^{*}|\geq
f(D)-60$.

###### Proof.

Suppose that $G$ is a 2-degenerate graph with $\Delta(G)\leq D$ and
$S\subseteq V(G)$ is a clique in $G^{2}$ with $|S|=f(D)>\frac{5}{2}D$. Note
that $G$ has a subgraph $G^{\prime}$ which satisfies that

  * (1)

$S$ is a clique of $G^{\prime 2}$, and

  * (2)

every edge $e\in E(G^{\prime})$ has an endpoint in $S$.

Without loss of generality, we assume that $G$ and $S$ satisfy (1) and (2).
Let $\sigma$ be a vertex order witnessing that $G$ is 2-degenerate. Subject to
this, choose $\sigma$ so the first vertex in $S$ appears as late as possible
in $\sigma$.

Since $G$ is 2-degenerate with maximum degree at most $D$, the degeneracy of
$G^{2}$ is at most $(D-2)+2(D-1)=3D-4$. Therefore, $f(D)\leq 3D-3$. By using
the discharging method, we show that there is a subgraph $G^{*}$ of $G$ which
is nice w.r.t. a clique $S^{*}$ in ${(G^{*})}^{2}$ and $|S^{*}|\geq f(D)-60$.

2453671245367black1black1453671 black21 black2black1$\downarrow$45671 black2
31 black2black3black15671 black2 3 black42 black3 4black1672 black3 4 5 black1
2 4 black57black1 2 3 4 black5
6$\leftarrow$$\leftarrow$$\leftarrow$$\rightarrow$$\rightarrow$ Figure 8: A
portion of a 2-degenerate graph $G$ and the positions of its tokens as its
vertices are deleted in a 2-degeneracy order; here $S=\\{1,\ldots,7\\}$. The
number of each token indicates the vertex where the token originated. Primary
tokens are shown in bold. At each vertex, we show at most one token received
from each other vertex. This Figure is reproduced from [3] with permission of
the authors.

We delete the vertices of $G$ one by one according to their occurrences in the
order $\sigma$. Once a vertex $v$ in $S$ is deleted, vertex $v$ gives a
“primary” token to each of its neighbors later in $\sigma$. Moreover, once a
vertex $v$ that currently possesses $s$ primary tokens (for some $s>1$) is
deleted, $v$ gives to each of its neighbors later in $\sigma$ exactly $s$
“secondary” tokens (see Figure 8). We emphasize here that Figure 8 is
reproduced from [3] with permission of the authors.

By this process, we show that there is a subgraph $G^{*}$ of $G$ which is
2-degenerate, witnessed by a vertex order $\sigma^{*}$, and $G^{*}$ is nice
w.r.t. a clique $S^{*}$ in ${(G^{*})}^{2}$. Then, by discharging method, we
show that $|S|-|S^{*}|\leq 60$. Let tokens($v$) (resp. primary($v$)) denote
the number of tokens (resp. primary tokens) that each vertex $v$ holds
immediately before it is deleted.

######  Claim 5.1.

If $v\in S$ and $w_{1}$, $w_{2}$ are the neighbors of $v$ later in $\sigma$,
if they exist, then

$1+\textnormal{tokens}(v)+D+\textnormal{primary}(w_{1})+\textnormal{primary}(w_{2})+6\geq|S|>\frac{5}{2}D.$
($\mathcal{F}$)

###### Proof.

Let $v\in S$. Recall that $S\subseteq N_{G^{2}}(v)$, i.e., $v$ is adjacent to
every vertex in $S$ in the graph $G^{2}$. Let $w$ be a neighbor of $v$ in $G$
which precedes $v$ in $\sigma$. Then, there is at most one vertex $x$ in
$N_{G}(w)\cap S$ from which $v$ receives no token (neither primary nor
secondary), so, the total number of such $x$ in $S$ is at most $D$. Each other
adjacency in $G^{2}$ between $v$ and a verte in $S$ must be accounted for
either (a) by a token received by $v$ or (b) by a primary token that has been
or will be received by $w_{1}$ or $w_{2}$ or (c) by being an adjacency to
$w_{1}$ or $w_{2}$ or to a neighbor of some $w_{i}$ that comes later than
$w_{i}$ in $\sigma$ (as shown in Figure 9 where each vertex in
$\\{v_{1},v_{2}\\}$, $\\{v_{3},v_{4},v_{5},v_{8}\\}$ and
$\\{w_{1},v_{6},v_{7},w_{2},v_{9},v_{10}\\}$ are respectively accounted by
(a), (b) and (c)). Note that at most $\textnormal{tokens}(v)$ vertices of $S$
are handled by (a), and at most 6 vertices of $S$ are handled by (c). The
number handled by (b) is at most
$\textnormal{primary}(w_{1})+\textnormal{primary}(w_{2})$. This implies
($\mathcal{F}$). Thus, the claim holds. ∎

$v_{1}$$v_{2}$$w$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$x$$v$$w_{1}$$w_{2}$later
Figure 9: Adjacencies between $v$ and vertices in $S$ in $G$ w.r.t occurrences
in $\sigma$.

In order to analyze the movement of tokens, we define Big, Basic, and Nonbasic
as follows.

######  Definition 5.2.

  1. (1)

$\textnormal{{Big}}:=\\{v\in V(G):\textnormal{primary}(v)>\frac{1}{4}D-4\\}$.

  2. (2)

$\textnormal{{Basic}}:=\\{v\in S:\textnormal{tokens}(v)<\frac{1}{4}D-4\\}$ and
$\textnormal{{Nonbasic}}:=S\setminus\textnormal{{Basic}}$.

Note that $\textnormal{{Big}}\cap\textnormal{{Basic}}=\emptyset$ while the
relationship between Big and Nonbasic is unclear. Now, we consider the sum of
the number of tokens at each vertex. For each $v$ in $S$, $v$ gives primary
tokens to at most two vertices, and each of those vertices gives secondary
tokens (due to $v$) to at most two more vertices. Thus, the contribution of
$v$ to the total number of tokens held by vertices at any point is at most 6.
So,

$\sum_{v\in V(G)}\textnormal{tokens}(v)\leq 6|S|\leq 18D$ ($\mathcal{G}$)

which implies that
$|\textnormal{{Nonbasic}}\cup\textnormal{{Big}}|\leq\frac{18D}{\frac{D}{4}-4}<73$.

We proceed to show the existence of $G^{*},S^{*}$ and $\sigma^{*}$.

######  Claim 5.3.

Each vertex $v\in\textnormal{{Basic}}$ has two neighbors later in $\sigma$
that are both in Big.

###### Proof.

Let $v\in\textnormal{{Basic}}$ and let $w_{1}$, $w_{2}$ be the neighbors of
$v$ later in $\sigma$, if they exist. Combining $v$ being basic with inequaty
$\mathcal{F}$, we have that

$\textnormal{primary}(w_{1})+\textnormal{primary}(w_{2})>\frac{5}{4}D-3.$

Since each vertex of $G$ has at most $D$ neighbors in $S$, we have that
$\textnormal{primary}(w_{i})\leq D$ for each $i\in\\{1,2\\}$. This implies
that $\textnormal{primary}(w_{i})>\frac{1}{4}D-4$, for each $i\in\\{1,2\\}$.
Thus, the claim holds. ∎

Let $W:=\\{w:w\in N(v)$ for some $v\in\textnormal{{Nonbasic}}$ and $w$ appears
later in $\sigma$ than $v\\}$. Now we start the construction of $G^{*}$,
$S^{*}$, $\sigma^{*}$.

######  Construction 5.4.

  * (1)

Let $S^{*}:=\textnormal{{Basic}}\setminus W$.

  * (2)

Move Big to the end of $\sigma$ (after the final vertex of $S^{*}$) and move
$(\textnormal{{Nonbasic}}\cup W)\setminus\textnormal{{Big}}$ to the start of
$\sigma$ (before the first vertex of $S^{*}$); call the resulting order
$\sigma^{*}$.

  * (3)

Delete every edge of $G$ with both endpoints outside $S^{*}$; call the
resulting graph $G^{*}$.

Now, we prove that $G^{*}$, $S^{*}$, $\sigma^{*}$ are exactly what we want.

######  Claim 5.5.

$S^{*}$ appears consecutively in $\sigma^{*}$, and $S^{*}$ and
$V(G^{*})\setminus S^{*}$ are independent sets of $G^{*}$.

###### Proof.

First, we show that $S^{*}$ appears consecutively in $\sigma^{*}$. Suppose, to
the contrary, that there is a vertex $v\notin S^{*}$ appears between $u\in
S^{*}$ and $w\in S^{*}$ in the order $\sigma^{*}$. Note that, by Construction
5.4(2), we have that $v\notin\textnormal{{Big}}\cup\textnormal{{Nonbasic}}\cup
W$. It implies that $v\notin S$ since
$S=\textnormal{{Basic}}\cup\textnormal{{Nonbasic}}$. Thus, $v\in V(G)\setminus
S$. Since the first vertex of $S$ appears as late as possible in $\sigma$ and
each edge has an endpoint in $S$, we have that $N_{G}(v)\cap S\neq\emptyset$
which implies that $v$ is a later neighbor in $\sigma$ of some vertex $x$ in
$S$, otherwise, we may move $v$ before the first vertex of $S$ which
contradicts the choice of $\sigma$. If $x\in\textnormal{{Basic}}$, then by
Claim 5.3, we have that $v\in\textnormal{{Big}}$, a contradiction. Then, we
have that $x\in\textnormal{{Nonbasic}}$ which implies that $v\in W$ by the
definition of $W$, a contradiction. Therefore, $S^{*}$ appears consecutively
in $\sigma^{*}$.

Observe that by Construction 5.4(3), $V(G^{*})\setminus S^{*}$ is an
independent set of $G^{*}$. Thus, it suffices to show that $S^{*}$ is an
independent set of $G^{*}$. Suppose that there is an edge between two vertices
$u$ and $w$ in $S^{*}$ where $w$ is a later neighbor of $u$ in $\sigma$. Since
$u$ belongs to Basic, by Claim 5.3, we have $w\in\textnormal{{Big}}$, a
contradiction. Therefore, the claim holds. ∎

The following two claims were proved in [3]. So, we just state the claims and
those proofs.

######  Claim 5.6.

$G^{*}$ is 2-degenerate, as witnessed by $\sigma^{*}$.

###### Proof.

Consider steps (2) and (3) above. Suppose we move some
$v\in\textnormal{{Big}}$ to the end of $\sigma$. If $v$ has a neighbor $w$
later (in $\sigma$), then $w\notin\textnormal{{Basic}}$, so $w\notin S^{*}$.
Thus, in step (3) we delete edge $vw$. Suppose instead that we move a vertex
$v\in W\cup\textnormal{{Nonbasic}}\setminus\textnormal{{Big}}$ to the start of
$\sigma$. If $v\in W\setminus\textnormal{{Big}}$ has a neighbor $w$ earlier
(in $\sigma$), then by the definition of $W$, we have that
$w\notin\textnormal{{Basic}}$; if
$v\in\textnormal{{Nonbasic}}\setminus\textnormal{{Big}}$ has a neighbor $w$
earlier (in $\sigma$), then by Claim 5.3, we have that
$w\notin\textnormal{{Basic}}$. Thus, for both cases, we have that $w\notin
S^{*}$ and so again in step (3) we delete $vw$. Therefore, $\sigma^{*}$ is a
2-degeneracy order for $G^{*}$ because $\sigma$ is a 2-degeneracy order for
$G$. ∎

######  Claim 5.7.

$S^{*}$ forms a clique in ${(G^{*})}^{2}$.

###### Proof.

Every edge deleted when forming $G^{*}$ has both endpoints outside of $S^{*}$.
But deleting such edges cannot impact adjacency in ${(G^{*})}^{2}$ between two
vertices in $S^{*}$. Thus, ${(G^{*})}^{2}[S^{*}]=G^{2}[S^{*}]$. ∎

Now, we finish the proof of Theorem 2.5 by showing that $|S\setminus
S^{*}|\leq 60$.

######  Claim 5.8.

$|S\setminus S^{*}|<61$.

###### Proof.

Let $X:=\textnormal{{Big}}\cup\textnormal{{Nonbasic}}\cup W$. Note that by
Construction 5.4(1), we have that $|S\setminus S^{*}|\leq|X|$. To show that
$|X|<61$, we use a discharging argument. Every $x$ in $X$ has an initial
charge $\textnormal{tokens}(x)$. After distributing charge, we show that each
$x$ in $X$ has charge at least $\frac{D}{4}-4$. Then by inequality
($\mathcal{G}$), we have

$|S\setminus
S^{*}|\leq|X|\leq\frac{6|S|}{\frac{D}{4}-4}\leq\frac{18D}{\frac{D}{4}-4}\leq
73,$

since $D>1732$. So, by Theorem 2.3, we have $|S|\leq\frac{5}{2}D+72$. Hence
since $D>1732$, if we substitute the bound $|S|\leq\frac{5}{2}D+72$ into the
inequality $\sum_{v\in V(G)}\textnormal{tokens}(v)\leq 6|S|$ again, we have
the following inequality

$|S\setminus S^{*}|\leq|X|\leq\frac{6|S|}{\frac{D}{4}-4}\leq\frac{15D+6\times
72}{\frac{D}{4}-4}=60+\frac{12\times 144}{D-4}<61$

which completes the proof of the claim.

Now we distrbute the charges. For $x\in X$, let $w_{1}$ and $w_{2}$ be the
neighbors of $x$ that follow $x$ in $\sigma$ (if they exist). Note that by the
definition of $W$, it suffices to consider each
$x\in\textnormal{{Big}}\cup\textnormal{{Nonbasic}}$ (note that this union does
not include $W$) and distribute charge so that $x$, $w_{1}$, and $w_{2}$ all
finish with charge at least $\frac{D}{4}-4$.

Suppose that $x\in\textnormal{{Big}}$. By definition,
$\textnormal{primary}(x)>\frac{D}{4}-4$ which also implies that
$\textnormal{tokens}(w_{i})>\frac{D}{4}-4$ since
$\textnormal{tokens}(w_{i})\geq\textnormal{primary}(x)$ for each
$i\in\\{1,2\\}$. So $x$ does not need to give charge to any neighbor later in
$\sigma$. Thus, $x$ (and each of its later neighbors) finishes with charge at
least $\frac{D}{4}-4$.

Suppose that $x\in\textnormal{{Nonbasic}}\setminus\textnormal{{Big}}$. If
$\textnormal{tokens}(x)\geq\frac{3}{4}D-12$, then $x$ gives charge
$\frac{D}{4}-4$ to each of its at most two neighbors that follows it in
$\sigma$. Thus, we assume that
$\frac{D}{2}-8\leq\textnormal{tokens}(x)<\frac{3}{4}D-12$. By inequality
($\mathcal{F}$), we have that

$\textnormal{primary}(w_{1})+\textnormal{primary}(w_{2})>\frac{3}{4}D+5$

and so $\textnormal{primary}(w_{i})\geq\frac{D}{4}-4$ for some
$i\in\\{1,2\\}$. Thus, at least one later neighbor of $x$ is big. So $x$ gives
charge $\frac{D}{4}-4$ to at most one neighbor later in $\sigma$. Thus, $x$
(and each of its later neighbors) finishes with charge at least
$\frac{D}{4}-4$.

Finally, suppose that $\frac{D}{4}-4\leq\textnormal{tokens}(x)<\frac{D}{2}-8$.
By inequality ($\mathcal{F}$), we have that

$\textnormal{primary}(w_{1})+\textnormal{primary}(w_{2})>D+1.$

Thus, $w_{i}\in\textnormal{{Big}}$ for at least one $i\in\\{1,2\\}$, so
$w_{i}$ needs no charge from $x$. If $w_{1}$, $w_{2}\in\textnormal{{Big}}$,
then neither $w_{i}$ receives charge from $x$, so $x$ (and each $w_{i}$)
finishes with charge at least $\frac{D}{4}-4$. Suppose instead, by symmetry,
that $w_{1}\in\textnormal{{Big}}$ and $w_{2}\notin\textnormal{{Big}}$. Since
$\textnormal{primary}(w_{i})\leq D$, we know that

$\textnormal{tokens}(x)+\textnormal{primary}(w_{2})>\frac{D}{2}-7.$

Thus, $x$ gives to $w_{2}$ charge $\textnormal{tokens}(x)-(\frac{D}{4}-4)$.
Clearly, $x$ finishes with charge at least $\frac{D}{4}-4$. Furthermore,
$w_{2}$ ends with charge at least

$\textnormal{primary}(w_{2})+\textnormal{tokens}(x)-\left(\frac{D}{4}-4\right)>\frac{D}{2}-7-\left(\frac{D}{4}-4\right)=\frac{D}{4}-3.$

Thus, each vertex of $X$ finishes with charge at least $\frac{D}{4}-4$. ∎

Therefore, Theorem 2.5 holds. ∎