On the Asymptotic Confirmation of the Faudree–Lehel Conjecture for General Graphs

Abstract

Given a simple graph G, the irregularity strength of G, denoted by s(G), is the least positive integer k such that there is a weight assignment on edges $f: E(G) \rightarrow \{1,2,\dots , k\}$ attributing distinct weighted degrees: $\tilde{f}(v):= \sum _{u: \{u,v\}\in E(G)} f(\{u,v\})$ to all vertices $v\in V(G)$. It is straightforward that $s(G) \ge n/d$ for every d-regular graph G on n vertices with $d>1$. In 1987, Faudree and Lehel conjectured in turn that there is an absolute constant c such that $s(G) \le n/d + c$ for all such graphs. Even though the conjecture has remained open in almost all relevant cases, it is more generally believed that there exists a universal constant c such that $s(G) \le n/{\delta }+ c$ for every graph G on n vertices with minimum degree ${\delta }\ge 1$ which does not contain an isolated edge; In this paper we confirm that the generalized Faudree–Lehel Conjecture holds for graphs with ${\delta }\ge n^\beta$ where $\beta$ is any fixed constant larger than 0.8; Furthermore, we confirm that the conjecture holds in general asymptotically. That is, we prove that for any $\varepsilon \in (0,0.25)$ there exist absolute constants $c_1, c_2$ such that for all graphs G on n vertices with minimum degree ${\delta }\ge 1$ and without isolated edges, $s(G) \le \frac{n}{{\delta }}(1+\frac{c_1}{{\delta }^{\varepsilon }})+c_2$; We thereby extend in various aspects and strengthen a recent result of Przybyło, who showed that $s(G) \le \frac{n}{d}\big (1+ \frac{1}{\ln ^{\varepsilon /19}n} \big )=\frac{n}{d}(1+o(1))$ for d-regular graphs with $d\in [\ln ^{1+\varepsilon } n, n/\ln ^{\varepsilon }n]$. We also improve the earlier general upper bound: $s(G)< 6\frac{n}{{\delta }}+6$ of Kalkowski, Karoński and Pfender.

1 Introduction

Let G be a simple graph. Consider an edge-weighting function $f: E(G)\rightarrow \{1,2,\dots , k\}$, where k is any positive integer. We call it a k-irregular assignment for G if the weighted degrees, denoted by $\tilde{f}(v) = \sum _{u\in N(v)} f(\{v,u\})$, are pairwise distinct for all $v \in V(G)$. The irregularity strength of G, denoted s(G), is the least positive integer k, if it exists, such that there is a k-irregular assignment for G; we set $s(G)=\infty$ for the remaining graphs. It is easy to see that $s(G) < \infty$ if and only if G has no isolated edges and has at most one isolated vertex.

The irregularity strength was first introduced by Chartrand, Jacobson, Lehel, Oellermann, Ruiz, and Saba [1], in particular in reference to research on irregular graphs [2,3,4]. Note that for any simple graph G, s(G) may naturally be alternatively set down as the least k such that one may produce an irregular multigraph by blowing each edge e of G to at most k copies of e, where by an irregular multigraph we mean a multigraph with pairwise distinct degrees. In general it is known that $s(G) \le n -1$ for any graph G of order n which is not a triangle and has finite irregularity strength. This was proved by Aigner and Triesch [5] and Nierhoff [6]. Though the family of stars witnesses the tightness of this upper bound, it can be greatly improved for graphs with larger minimum degree. In particular, already Faudree and Lehel [7] showed that $s(G) \le \lceil n/2 \rceil +9$ for every d-regular graph with $n, d\ge 2$. This was however still far from the expected optimal upper bound. By a simple counting argument, it is easy to see that

$$\begin{aligned}s(G) \ge \Bigg \lceil {\frac{n+d+1}{d}}\Bigg \rceil .\end{aligned}$$

This lower bound motivated Faudree and Lehel [7] to conjecture in 1987 that the value n/d is close to optimal. In fact, this conjecture was first posed by Jacobson, as mentioned in [8].

Conjecture 1

(Faudree–Lehel Conjecture [7]) There is a constant $c>0$ such that for all d-regular graphs G with n vertices and $d\ge 2$,

$$\begin{aligned}s(G) \le \frac{n}{d}+c.\end{aligned}$$

It is moreover believed that the following natural extension of the conjecture holds in general.

Conjecture 2

(Generalized Faudree–Lehel Conjecture [7]) There is a constant $c>0$ such that for all graphs G on n vertices with minimum degree ${\delta }\ge 1$ and without isolated edges,

$$\begin{aligned}s(G) \le \frac{n}{{\delta }}+c.\end{aligned}$$

It is this conjecture that “energized the study of the irregularity strength”, as stated in [9]. It also settled foundations for entire discipline, providing inspiration for many related papers, concepts and intriguing questions, see e.g. [5, 8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38]. The conjecture remains open after more than three decades since it was formulated. A significant step forward regarding it was achieved in 2002 by Frieze, Gould, Karoński, and Pfender [23], who used the probabilistic method. They proved the first linear in n/d bound $s(G) \le 48(n/d)+1$ for $d \le \sqrt{n}$, and a superlinear bound $s(G) \le 240(\log n)(n/d)+1$ when $d > \left\lfloor \sqrt{n} \right\rfloor$. Similar bounds for general graphs, with d replaced by the minimum degree $\delta$, were also proved in the same paper. These in particular imply that $s(G) = O(n/\delta )$ if G has maximum degree $\Delta \le n^{1/2}$. The linear bounds in n/d and $n/\delta$ were further extended to the cases when $d \ge 10^{4/3}n^{2/3}\log ^{1/3}n$ and $\delta \ge 10n^{3/4}\log ^{1/4}n$, respectively, by Cuckler and Lazebnik [9]. The first linear bounds in both n/d and $n/\delta$ for all ranges of n, d and $\delta$ were settled by Przybyło. He used a different idea to improve a key combinatorial lemma in [23], thus proving in [33, 34] that $s(G) \le 16(n/d)+6$ and, resp., $s(G) \le 112(n/\delta )+28$. Since then, considerable efforts were devoted to improve the multiplicative constant in front of n/d and $n/\delta$. In course of work over this and several related concepts a list of inventive and highly useful algorithms were developed in particular in [13, 25, 26, 28, 39]. These assured important breakthroughs concerning s(G) and other widely studied graph invariants. The best result among these is due to Kalkowski, Karoński and Pfender [25], who proved that in general $s(G) \le 6 \lceil n/\delta \rceil$ (what was later improved to $s(G) \le (4+o(1))(n/\delta )+4$ for a narrower range of $\delta \ge \sqrt{n}\log n$ in [28]). It was only until recently when Przybyło [30] proposed an algorithm which significantly improved the previous upper bounds for d-regular graphs. His result implies in particular that Conjecture 1 holds asymptotically (in terms of d and n) for d not in extreme values.

Theorem 3

(Przybyło [30]) Given any fixed $\varepsilon >0$, for every d-regular graph G with n vertices and $d\in [\ln ^{1+\varepsilon } n, n/\ln ^{\varepsilon }n]$, if n is sufficiently large,

$$\begin{aligned} s(G) \le \frac{n}{d}\left( 1+ \frac{1}{\ln ^{\varepsilon /19}n}\right) . \end{aligned}$$

In [30] Przybyło mentioned that “a poly-logarithmic in n lower bound on d is unfortunately unavoidable” within his approach. In this paper, we extend the range of d to bypass the poly-logarithmic in n lower bound (and the upper bound too). We also provide at the same time a stronger upper bound on s(G) for all $1\le d \le n-1$.

In the case of general graphs with minimum degree $\delta$, instead of regular graphs with degree d, obtaining a good bound on s(G) is considerably harder. The existing methods, applicable in the case of regular graphs, stop working for general graphs, or would result in a much worse bound. Prior to our result, no asymptotically sharp bound on s(G) has been shown for general graphs with minimum degree $\delta$. One exception is the family of random graphs G(n, p), where p is any fixed constant in (0, 1), for which the first author showed that $s(G) \le \lceil n/\delta \rceil +2$ almost surely [40]. In this paper, we are able to show that the generalized Faudree-Lehel Conjecture (Conjecture 2) also holds asymptotically.

Theorem 4

For every $\varepsilon \in (0,0.25)$, there are absolute constants $c_1, c_2$ such that for each graph G with n vertices and minimum degree ${\delta }>0$ which does not contain isolated edges,

$$\begin{aligned} s(G) \le \frac{n}{\delta }\left( 1+ \frac{c_1}{\delta ^{\varepsilon }}\right) +c_2.\end{aligned}$$

Note that Theorem 4 in particular implies (for $\varepsilon =0.2$) that $s(G)\le (n/\delta )(1+(c_1/\delta ^{0.2}))+c_2$ for some absolute constants $c_1,c_2$. For any fixed $\varepsilon >0$ (in Theorem 3) and $\delta \in [\ln ^{1+\varepsilon } n, n/\ln ^{\varepsilon }n]$, we however have: $(n/\delta )(1/\ln ^{\varepsilon /19}n) \gg (n/\delta )(c_1/\ln ^{0.2+0.2\varepsilon }n) \ge (n/\delta )(c_1/\delta ^{0.2})$ and $(n/\delta )(1/\ln ^{\varepsilon /19}n) \ge (\ln ^\varepsilon n) (1/\ln ^{\varepsilon /19}n) \gg c_2$. Thus our bound is in particular a direct improvement over the bound in Theorem 3 (which additionally regards only the case of regular graphs).

Moreover, as the second contribution of the paper, which seems even more or equally vital as the one above, we also confirm that the Faudree-Lehel Conjectures (Conjectures 1 and 2) hold, not only asymptotically, for all graphs with $\delta \ge n^\beta$ where $\beta$ is any fixed constant greater than 0.8.

Theorem 5

For every $\varepsilon \in (0, 0.25)$, there is an absolute constant c such that for each graph G with n vertices and minimum degree $\delta \ge n^{1/(1+\varepsilon )}$,

$$\begin{aligned}s(G) \le \frac{n}{\delta } + c.\end{aligned}$$

2 Tools and Notation

We will use the following tools.

Lemma 6

(Chernoff Bound, c.f., e.g., [41], Appendix A) Let $X_1, \dots , X_n$ be i.i.d. random variables such that $\Pr (X_i=1) = p$ and $\Pr (X_i=0)=1-p$. Then for any $t \ge 0$,

$$\begin{aligned} \Pr \left( \left| \sum _{i=1}^n X_i - np\right|> t\right) \le 2e^{-t^2/(3np)}, \ \ {}&\text { if } 0 \le t \le np, \\ \Pr \left( \left| \sum _{i=1}^n X_i - np\right|> t\right) \le 2e^{-t/3}, \ \ {}&\text { if } t > np. \end{aligned}$$

Corollary 7

(Chernoff Bound, c.f., e.g., [41], Appendix A) Let $X_1, \dots , X_n$ be i.i.d. random variables such that $\Pr (X_i=1) = p$ and $\Pr (X_i=0)=1-p$. Then for any $t \ge 0$,

$$\begin{aligned} \Pr \left( \left| \sum _{i=1}^n X_i - np\right| > t\right) \le 2e^{-t^2/3\max (np, t)}. \end{aligned}$$

Definition 8

(Negative Association [42]) A set of random variables $X_1, \dots ,X_n$ are negatively associated if for any two disjoint index sets $I, J \subset [n]$ and two monotone increasing functions $f,g: \mathbb {R} \rightarrow \mathbb {R}$, $\mathbb {E}[f(X_i, i\in I) g(X_j, j\in J)] \le \mathbb {E}[f(X_i, i\in I)] \mathbb {E}[ g(X_j, j\in J)].$

Lemma 9

(Zero–one Principle [42]) Let $X_1, \dots ,X_n$ be zero–one random variables such that always $\sum _i X_i \le 1$. Then $X_1, \dots , X_n$ are negatively associated.

Lemma 10

(Closure Property [42]) Let $X_1, \dots ,X_n$ be negatively associated and let $Y_1, \dots , Y_n$ be negatively associated. If $\{X_i\}_i$ are independent from $\{Y_i\}_i$, then $\{X_i\}_i \cup \{Y_i\}_i$ are negatively associated.

Lemma 11

(Chernoff Bound [42]) Let $X_1,\dots , X_n$ be negatively associated random variables such that $\Pr (X_i=1)=p$ and $\Pr (X_i=0)=1-p$. Then the two Chernoff Bounds in Lemma 6 hold.

Lemma 12

(Simple Concentration Bound [43]) Let S be a random variable determined by n independent trials $X_1,\ldots ,X_n$, and satisfying: changing the outcome of any one trial can affect S by at most $c>0$. Then for any $t>0$,

$$\begin{aligned} \Pr \left( \left| S - \mathbb {E}(S)\right| > t\right) \le 2e^{-t^2/(2c^2n)}. \end{aligned}$$

Given a graph G, a set $U \subset V(G)$ and a vertex $v \in V(G)$, we use $\deg _U(v)$ to denote the number of neighbors of v in U. We use G[U] to denote the subgraph induced by U in G, and E(U) to be the set of edges of G[U].

Throughout the paper we assume that the graph G has n vertices and minimum degree $\delta$. A weighted degree of a vertex v will usually be abbreviated as a weight of v.

3 General Proof Idea, Links and Obstacles

The basic intuition behind our construction is to partition V(G) into a big set B and a small set S, where $|S| = (n/{\delta })\cdot o({\delta })$. We first adjust the edge weights so that almost all vertices in B have distinct weights. Then we locally adjust weights of the rest of the vertices to distinguish the weights of all vertices in G.

Our argument can be divided into three main steps. Step A relies on a specific random construction, which assures relatively sparse distribution of weights of the vertices in B, i.e. without too many vertex weights in any of the predefined intervals partitioning positive integers. Step B consists of modifications of the weights of edges across B and S, aiming at generating relatively small shifts of the vertex weights in B. As a result, pairwise distinct weights will be attributed to all but a small set of bad vertices in B. (We note here that S must be large enough to provide sufficiently many edges across B and S for our purposes.) In step C we modify weights of the edges in S and a small portion of the edges outside S in order to weight distinguish the vertices in S mostly. For this aim we attribute these vertices special weights deliberately unused in step B (with residues at most 5 modulo a carefully chosen and large enough integer k). To distinguish weights in S we in particular benefit from the fact that this set is small compared to B, and thus vertices in S have on average large fraction of all their incident edges in E(S, B) (usually much larger than the fraction of their incident edges in S). This enables taking on vital preparatory measures prior to step C (within step A), ensuring sparse vertex weight distribution in S and facilitating the mentioned final cleanup in this set. Throughout the construction we moreover single out several types of “bad vertices”, which do not fulfill one of a number of specified conditions, and cannot be weight distinguished according to major procedures. The set of all of these is however small enough to be handled with in a special manner in step C.

Our approach is motivated by the random construction idea from [30], which amounts to show that under certain conditions there are no “bad vertices”at all (in case of regular graphs). Then an explicit weight assignment could be provided in the face of absence of such problematic vertices. Typically, if the minimum degree $\delta$ is $\Omega (\log n)$, then a union bound could be used to prove that with positive probability there are no “bad vertices”resulting from the random construction. To bypass the $\log n$ factor, careful quantization and the Lovász Local Lemma turned out to be very helpful tools in the case of regular graphs. In fact in [44] we provide a significantly more simple approach, yielding similar results as the ones in this paper, but for the setting restricted to regular graphs exclusively. To prove the asymptotic bound for all ${\delta }$ in the case of general graphs, one of the real challenges is that the maximum degree and minimum degree could differ by any factor. This in particular forefends a direct application of the Lovász Local Lemma. In this paper we bypass all these difficulties. One of our main ideas is that although we cannot guarantee that there are no “bad vertices”at all resulting from the random construction, yet the number of such bad vertices cannot be too large (in fact it is usually exponentially small). We therefore can accumulate these bad vertices and treat them at the end of the proof via careful and technical analysis.

4 Proof of Main Results

4.1 Set-Up

We will focus on proving Theorem 4. Only at the very end of the paper do we comment on how it directly implies Theorem 5. Let us thus fix $\varepsilon$, corresponding to Theorem 4, followed by an auxiliary small constant $\alpha$ such that

$$\begin{aligned} \varepsilon \in (0,0.25),~~~~~~{ \alpha \in (0,\varepsilon )}~~~~~~\textrm{and}~~~~~~{ 2\varepsilon +\alpha <0.5}, \end{aligned}$$

(1)

and a graph G. Let $X_v\sim U[0,1]$, for $v \in V(G)$ be i.i.d.  uniform random variables. These are used to separate the vertices into $\delta$ bins. For $1 \le i \le {\delta }-1$, let the i-th bin be defined as

$$\begin{aligned}B_i = \{v: (i-1)/{\delta }\le X_v < i/{\delta }\},\end{aligned}$$

and set the last bin as $B_{\delta }= \{v: ({\delta }-1)/{\delta }\le X_v \le 1\}$. In expectation, every $B_i$ includes $n/{\delta }$ vertices. For each vertex v, we define:

$$\begin{aligned}\mathrm{the~ random~ variable~} Z(v) \in [1, {\delta }] ~\mathrm{to~ be~ the~ bin~ number~} i~ \mathrm{such~ that~} v\in B_i.\end{aligned}$$

Let the small set S be the union of bins $B_{i}$ with $i > {\delta }- {s^*}$ where

$$\begin{aligned} {s^*}: =\Bigg \lceil {{\delta }^{1/2+{ \varepsilon +\alpha }}}\Bigg \rceil . \end{aligned}$$

Thus the expected number of vertices in S is $n{s^*}/{\delta }\ll _{{\delta }} n$. Denote $B:= V(G) {\setminus } S$ to be the big set.

In order to take on certain preparatory measures prior to Step C (within which we will finally distinguish weights of the vertices in S), we will further partition S into $k'$ similar sized subsets where

$$\begin{aligned} { k':= \min \left( \Bigg \lceil {\frac{n}{400{\delta }}}\Bigg \rceil \Bigg \lceil {\frac{{\delta }^{\varepsilon }}{2000}}\Bigg \rceil \right) }.\end{aligned}$$

Each such subset will consist of $\lceil {s^*}/k' \rceil$ or $\left\lfloor {s^*}/k' \right\rfloor$ bins. More specifically, for $i=1$, let $S_1$ be the union of the first $\left\lfloor {s^*}/k' \right\rfloor$ bins in S, i.e., $S_1 = \{ \bigcup B_j: {\delta }-{s^*}< j \le {\delta }{ -{s^*}+\left\lfloor {s^*}/k' \right\rfloor }\}$. Next, sequentially define $S_2, \dots , S_{k'}$ so that $S_j$ is the union of the first $\left\lfloor {s^*}/k' \right\rfloor$ or $\lceil {s^*}/k' \rceil$ (depending on ${s^*}\mod k'$) consecutive yet ungrouped bins in S. Furthermore, set

$$\begin{aligned} k: = \Bigg \lceil {k'/1000}\Bigg \rceil ~~~~\textrm{and}~~~~a': = \Bigg \lceil {{ 7}\Bigg \rceil n/({\delta }k)}. \end{aligned}$$

These two parameters will be used in Step A.

We will show that when $\delta$ or $n/\delta$ is smaller than a constant c, then Theorem 4 holds. Thus, throughout the computations in the paper, unless otherwise stated, we will assume there is an absolute constant c such that $\delta \ge c$, $n/\delta \ge c$ and c is large enough so that all explicit inequalities in the computations hold.

4.2 Step A

Definition 13

We define a weighting assignment $f_1: E(G) \rightarrow \mathbb {Z}$ in Step A as follows.

• 1. For every bin number $1 \le i \le \delta - {s^*}$, for each vertex $v\in B_i \subset B$ and each of its neighbors u in $\{\bigcup B_j, {\delta -s^*-i+1< j \le \delta -s^*}\}\subset B$, let $f_1(\{u,v\})$ be equal to $\lceil n/{\delta } \rceil +a'$.

• 2. For every integer $1 \le j \le k'$, for each vertex $v\in B$ and its neighbor $u \in S_j$, let $f_1(\{u,v\})$ be equal to $\lceil \lceil n/{\delta } \rceil /{3k'} \rceil (j+k').$

• 3. Let $f_1$ equal 1 on the rest of the edges in B, and let $f_1$ equal 0 on the edges in S.

Let $\tilde{f}_1: V(G) \rightarrow \mathbb {Z}$ evaluate the weights of vertices under $f_1$.

Definition 14

Let $\sigma (v,i)$ be the random vertex weight $\tilde{f}_1(v)$ given $v \in B_i$. Let $I_0= (0, (\lceil n/{\delta } \rceil +a'-1)),$ whereas for each integer $1 \le h < { 2}n$, we define the interval

$$\begin{aligned} I_h= [ h(\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-1), (h+1)(\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-1)). \end{aligned}$$

For each $1\le i \le {\delta }-{s^*}$ and each vertex v, denote the expected weight of v if $v\in B_i$ as

$$\begin{aligned} \sigma _\mu (v,i) = \mathbb {E}\left[ \tilde{f}_1(v) \,\vert \,v\in B_i\right] \end{aligned}$$

and set $\sigma _\mu (v,i)=0$ for ${\delta }-{s^*}< i\le \delta$ and $v\in V(G)$. For $0\le h < 2n$, let $\mu _h$ be the expected number of vertices in G such that $\sigma _\mu (v, Z(v)) \in I_h$ (note all these vertices must belong to B). Given integers $0 \le h_1 \le h_2$, let

$$\begin{aligned}\mu _{[h_1, h_2)} = \sum _{h=h_1}^{h_2-1}\mu _h.\end{aligned}$$

Note that since $0 \notin I_0$, then $\sigma _\mu (v, i) \notin I_h$ for all $h \ge 0$ if $i > \delta - {s^*}$.

By Definition 13,

$$\begin{aligned} \Vert \tilde{f}_1\Vert _\infty \le \max _v \deg (v) (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a') \le (n-1)(\Bigg \lceil {n/{\delta }}\Bigg \rceil +a') < 2n(\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-1), \end{aligned}$$

(2)

and thus $\mu _{[0, 2n)} =\mathbb {E}(|B|)$.

Claim 15

Let v be a fixed vertex and i an integer in $[1, {\delta }-{s^*}]$. Given $v \in B_i$, with probability at most $2e^{-{\delta }^{2{ \alpha }}/2}$, $\left| \sigma (v,i)- \sigma _\mu (v,i)\right| > \deg (v)^{1/2+{ \alpha }} \left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$. In addition, for each vertex v and a fixed integer $h \in [0, 2n)$, there is at most one bin i such that ${ \sigma _\mu }(v,i)\in I_h$. This implies $\mu _h \le n/{\delta }$.

Proof

Fix any $i\in [1, {\delta }-{s^*}]$. Given $v\in B_i$, the expected value of $\sigma (v,i)$ equals $\sigma _\mu (v,i)$ and is determined by the values of $\deg (v)$ independent variables $X_v$, $v\in N(v)$. As by definition of $f_1$, changing the outcome of any one of these variables can affect $\sigma (v,i)$ by at most $\left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$, the Simple Concentration Bound (Lemma 12) implies that the probability that $\left| \sigma (v,i)- \sigma _\mu (v,i)\right| > \deg (v)^{1/2+{ \alpha }} \left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$ is at most

$$\begin{aligned} 2e^{-\deg (v)^{1+2{ \alpha }} \left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) ^2/(2\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) ^2\deg (v))} \le 2e^{-\delta ^{2{ \alpha }}/2}, \end{aligned}$$

as desired.

To prove our second claim, we need to approximate $\sigma _\mu (v,i)$. This is equal to $w_\mathbb {E}(v,i, B)+ w_\mathbb {E}(v,i, S)$ where $w_\mathbb {E}(v,i, B)$ and $w_\mathbb {E}(v,i, S)$ denote the expected weights of v coming from its neighbors in B and S, respectively, given that $v\in B_i$. Let us denote for simplicity: $B^i = \{\cup B_j, \delta -{s^*}- i + 1 < j \le \delta - {s^*}\}$. The probability that a fixed neighbor of v lies in $B^i$ equals exactly $(i-1)/{\delta }$. Thus, the expected number of neighbors of v lying in $B^i$ equals $\deg (v) \frac{i-1}{{\delta }}$. Similarly, the expected number of neighbors of v lying in $B \setminus B^i$ equals $\deg (v) \frac{{\delta }- {s^*}- i+1}{{\delta }}$. Therefore,

$$\begin{aligned} w_\mathbb {E}(v,i, B)&= (\lceil n/{\delta }\rceil + a') \mathbb {E}[\deg _{B^i}(v)] +1 \cdot \mathbb {E}[\deg _{B \setminus B^i}(v)] \nonumber \\&= \deg (v) \frac{i-1}{{\delta }}\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) + 1 \cdot \deg (v) \frac{{\delta }- {s^*}- i+1}{{\delta }} \nonumber \\&= \frac{ \deg (v) }{{\delta }} \left( (i-1)\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a' -1 \right) +{\delta }-{s^*}\right) . \end{aligned}$$

(3)

On the other hand, by condition 2 in the definition of $f_1$, the expected value $w_\mathbb {E}(v,i, S)$ does not depend on i. Thus, it is equal to some number $w_\mathbb {E}(v,S)$, whose precise value is irrelevant within our proof. Combining this fact with (3), we obtain that

$$\begin{aligned} \sigma _\mu (v,i)&= \ w_\mathbb {E}(v,i, B)+ w_\mathbb {E}(v,i,S) = \ \frac{\deg (v)}{{\delta }} \left( (i-1)\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) +{\delta }-{s^*}\right) \\&\quad + w_\mathbb {E}(v,S). \nonumber \end{aligned}$$

Therefore, $\sigma _\mu (v,i)\in I_h$ implies that

$$\begin{aligned} h\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right)&\le \frac{\deg (v)}{{\delta }} \left( (i-1)\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) +{\delta }-{s^*}\right) \\&\quad + w_\mathbb {E}(v,S) <(h+1)\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) . \end{aligned}$$

Rearranging the inequalities, we have:

$$\begin{aligned} \frac{{\delta }h}{\deg (v)} - \frac{{\delta }-{s^*}+ \frac{\delta }{\deg (v)}w_\mathbb {E}(v,S)}{\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1} \le i - 1 < \frac{{\delta }(h+1)}{\deg (v)} - \frac{{\delta }-{s^*}+ \frac{\delta }{\deg (v)}w_\mathbb {E}(v,S)}{\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1}. \end{aligned}$$

Thus, in order to make $\sigma _\mu (v,i) \in I_h$, i has to lie in an interval (with one end open) of length ${\delta }/\deg (v) \le 1$. Therefore, given h and v, there is at most one integer $i \le {\delta }-{s^*}$ such that $\sigma _\mu (v,i) \in I_h$. The probability that v lies in the corresponding bin (if exists) equals $1/{\delta }$. Thus, $\mu _h \le \sum _{v \in V(G)} (1/{\delta }) = n/{\delta }.$ $\square$

Definition 16

Given an integer $0\le h < 2n$, let $V_h$ be the set of vertices such that $\sigma _\mu (v, Z(v)) \in I_h$ and $\left| \sigma (v,Z(v))- \sigma _\mu (v,Z(v))\right| \le \deg (v)^{1/2+{ \alpha }} \left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$.

Let $Z_{h}^B$ be the set of bad vertices such that $\sigma _\mu (v, Z(v)) \in I_h$ and $\left| \sigma (v,Z(v))- \sigma _\mu (v,Z(v))\right|$ > $\deg (v)^{1/2+{ \alpha }}$ $\left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$.

Given two integers $0\le h_1 \le h_2 \le 2n$, let

$$\begin{aligned} V_{[h_1, h_2) }= \bigcup _{h_1 \le h< h_2}V_h~~~~~~~~\textrm{and}~~~~~~~~Z_{[h_1, h_2)}^B= \bigcup _{h_1 \le h< h_2}Z_{h}^B.\end{aligned}$$

The sets $Z_{h}^B$ consist of the first kind of bad vertices in the proof. Clearly $V_h\cup Z_{h}^B$ is the set of all vertices v such that $\sigma _\mu (v,Z(v))\in I_h$, and thus, by (2), $V_{[0,2n)} \cup Z_{[0, 2n)}^B=B$.

Lemma 17

Given two integers $0\le h_1 <h_2 \le 2n$ such that $\mu _{[h_1, h_2)} > 1$, the following inequalities hold simultaneously with probability at least $1- e^{-{\delta }^{2\alpha }/4} -2\exp \left( -\frac{1}{{3}} \sqrt{\frac{n}{{\delta }^{1-2{\alpha }}}} \right)$:

$$\begin{aligned}&{ \left| V_{[h_1, h_2)}\right| \le \mu _{[h_1, h_2)} + \sqrt{ \frac{n\mu _{[h_1, h_2)}}{{\delta }^{1-2{\alpha }}}}; } \ \ \text {and} \end{aligned}$$

(4)

$$\begin{aligned}&\left| Z_{[h_1, h_2)}^B \right| {< 2}\mu _{[h_1, h_2)} {\exp ({-{\delta }^{2{\alpha }}/4})}. \end{aligned}$$

(5)

In addition, if ${\delta }> \sqrt{n}$, with probability at least $1-1/{n}$,

$$\begin{aligned}&Z_{[0, 2n)}^B = \emptyset . \end{aligned}$$

(6)

Proof

For each vertex v and integers $i \in [1, {\delta }-{s^*}]$, $h\in [0,{2}n)$, let a random variable $Y_{v,i,h}$ be the indicator function that $v\in B_i$ and $\sigma _\mu (v, i)\in I_h$. Define $Z_{v,i,h}$ to be equal to 1 if $v\in B_i$, $\sigma _\mu (v, i)\in I_h$ and $\left| \sigma (v,i)- \sigma _\mu (v,i)\right| > \deg (v)^{1/2+{ \alpha }} \left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$. Otherwise, set $Z_{v,i,h}=0$. Thus,

$$\begin{aligned}&|V_h| = \sum _{v\in V(G), 1\le i \le {\delta }-{s^*}} (Y_{v,i,h}-Z_{v,i,h}) ~~~ {\le \sum _{v\in V(G), 1\le i \le {\delta }-{s^*}} Y_{v,i,h},} \end{aligned}$$

(7)

$$\begin{aligned}&|Z_{h}^B|= \sum _{v\in V(G), 1\le i \le {\delta }-{s^*}}Z_{v,i,h}, \end{aligned}$$

(8)

$$\begin{aligned}&\mathbb {E}[\sum _{h_1 \le h< h_2}\sum _{v\in V(G)}\sum _{1\le i\le {\delta }- {s^*}} Y_{v,i,h}]= \sum _{h_1 \le h < h_2}\sum _{v\in V(G)}\sum _{1\le i\le {\delta }- {s^*}} \Pr (v \in B_i, \sigma _\mu (v,i)\in I_h)\nonumber \\&= \ \mu _{[h_1, h_2)}. \end{aligned}$$

(9)

By Claim 15,

$$\begin{aligned} \Pr (Z_{v,i,h}=1) =&\, \Pr \left( \left| \sigma (v,i)- \sigma _\mu (v,i)\right| > \deg (v)^{1/2+{\alpha }} \left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) \,\Big \vert \,{ v \in B_i} \right) \cdot \nonumber \\&\Pr (v\in B_i, \sigma _\mu (v,i)\in I_h) \nonumber \\ \le&\, {2e^{-{\delta }^{2{\alpha }}/2}} \Pr (v\in B_i, \sigma _\mu (v,i)\in I_h). \end{aligned}$$

(10)

Thus, together with (8), (10) and (9),

$$\begin{aligned} \mathbb {E}(|Z_{[h_1, h_2)}^B|) =&\, \sum _{h_1 \le h< h_2} \sum _{v\in V(G)}\sum _{1\le i \le {\delta }-{s^*}}\mathbb {E}(Z_{v,i,h})\\ =&\sum _{h_1 \le h< h_2} \sum _{v\in V(G)}\sum _{1\le i \le {\delta }-{s^*}}\Pr (Z_{v,i,h}=1) \\ \le&\, {2e^{-{\delta }^{2{\alpha }}/2}} \sum _{h_1 \le h < h_2}\sum _{v\in V(G)} \sum _{1\le i \le {\delta }-{s^*}}\Pr (v\in B_i, \sigma _\mu (v,i)\in I_h)\\ =&\, {2e^{-{\delta }^{2{\alpha }}/2}} \mu _{[h_1, h_2)}. \end{aligned}$$

Therefore, by Markov’s Inequality,

$$\begin{aligned} \Pr \left( |Z_{[h_1, h_2)}^B| \ge {2e^{-{\delta }^{2{\alpha }}/4}} \mu _{[h_1, h_2)}\right) \le \frac{\mathbb {E}(|Z_{[h_1, h_2)}^B|)}{ {2e^{-{\delta }^{2{\alpha }}/4}} \mu _{[h_1, h_2)}} \le \frac{ {2e^{-{\delta }^{2{\alpha }}/2}} \mu _{[h_1, h_2)}}{ {2e^{-{\delta }^{2{\alpha }}/4}} \mu _{[h_1, h_2)}}= {e^{-{\delta }^{2{\alpha }}/4}} . \end{aligned}$$

(11)

For the sake of (5) we will now bound the probability that $\sum _{h_1 \le h < h_2}\sum _v\sum _{1\le i\le {\delta }- {s^*}} Y_{v,i,h}$ is far from its expectation in (9). Note that for a fixed v, although there is no bin $B_i$ that vertex v must lie in, given any random experiment (evaluating $X_v$) there is exactly one bin $B_i$ that v belongs to, while $\deg (v)$ together with the bin $B_i$ determine the unique at most one value of h for which $\sigma _\mu (v,i)\in I_h$. Thus, the indicator random variables satisfy $\sum _{i, h} Y_{v,i,h} \le 1$, and hence, by Lemma 9, the random variables $\{Y_{v,i,h}\}_{i,h}$ are negatively associated. Furthermore, since the variables in $\{Y_{v,i,h}\}_{i,h}$ are independent from such variables corresponding to other vertices, by Lemma 10, the random variables in $\{Y_{v,i,h}\}_{v, h_1 \le h < h_2, 1\le i\le {\delta }- {s^*}}$ are negatively associated. Thus, leaving out the random variables $Y_{v,i,h}$ which are constantly zero, the rest are identically distributed and negatively associated. Hence, we may use the Chernoff Bound (Lemma 11) and the shorthand $Y =\sum _{h_1 \le h < h_2}\sum _v\sum _{1\le i\le {\delta }- {s^*}} Y_{v,i,h}$, where by (9), $\mathbb {E}[Y] = \mu _{[h_1, h_2)}$:

$$\begin{aligned} \Pr \left( \left| Y - \mu _{[h_1, h_2)}\right| > \sqrt{\frac{n\mu _{[h_1, h_2)}}{{{\delta }^{1-2{\alpha }}}}} \right)&\le 2\exp \left( -\frac{ n\mu _{[h_1, h_2)}/{{\delta }^{1-2{\alpha }}}}{3 \max \left( \sqrt{n\mu _{[h_1, h_2)} /{{\delta }^{1-2{\alpha }}}}, \mu _{[h_1, h_2)} \right) }\right) \nonumber \\&\le 2\exp \left( -\min \left( \frac{\sqrt{n\mu _{[h_1, h_2)} /{{\delta }^{1-2{\alpha }}}}}{3}, \frac{n}{{3}{\delta }^{1-2{\alpha }}} \right) \right) \nonumber \\&\le 2\exp \left( - \frac{\sqrt{n/{{\delta }^{1-2{\alpha }}}}}{3} \right) . \end{aligned}$$

(12)

Inequalities (11) and (12) thus imply  (4) and (5) (cf. (7)). Moreover, by (10),

$$\begin{aligned} \Pr (v \in Z_{[0,2n)}^B) =&\sum _{1\le i\le {\delta }-{s^*}, h\in [0,2n)} \Pr (Z_{v,i,h}=1) \le {2e^{-{\delta }^{2{\alpha }}/2}} \sum _{1\le i\le {\delta }-{s^*}} \sum _{h\in [0,2n)}\nonumber \\&\Pr (v\in B_i, \sigma _\mu (v,i)\in I_h) \end{aligned}$$

(13)

$$\begin{aligned} \le&\, {2e^{-{\delta }^{2{\alpha }}/2}} \sum _{1\le i\le {\delta }-{s^*}} \Pr (v\in B_i) <{2e^{-{\delta }^{2{\alpha }}/2}.} \end{aligned}$$

(14)

Thus, by a union bound over v, when ${\delta }> \sqrt{n}$, $\Pr \left( Z_{[0,2n)}^B = \emptyset \right) \ge 1 - n {2e^{-{\delta }^{2{\alpha }}/2}} > 1- 1/{n}$. $\square$

Since the degree distribution can vary in G, it will be useful to group $\mu _h$’s of smaller sizes. As by Claim 15, $\mu _h \le n/{\delta }$ for each integer h, we may define the following benchmarks to that end.

Definition 18

We can sequentially define the benchmarks $h^*_{1},h^*_{2}, \dots$ such that $h^*_{1}=0$ and

$$\begin{aligned} n/(2{\delta }) < \mu _{[h^*_{i},h^*_{i+1})} \le {2n/{\delta }}. \end{aligned}$$

(15)

Claim 19

The number of benchmarks is at most ${2{\delta }}$.

Proof

Since $\sum _{0\le h<2n} \mu _h {\le } n$, the claim holds by (15) [and (2)]. $\square$

By (15) and Claim 19 we may apply Lemma 17 to at most ${(2{\delta })^2 = 4{\delta }^2}$ distinct benchmark pairs $(h^*_{i}, h^*_{j})$ in order to conclude that the following union bound holds.

Corollary 20

With probability at least $1-{4}{\delta }^2 {e^{-{\delta }^{2{\alpha }}/4}} - {8}{\delta }^2\exp \left( -\frac{1}{{3}} \sqrt{\frac{n}{{\delta }^{1-2{\alpha }}}} \right)$, for any two benchmarks $h^*_{i} { <} h^*_{j}$, the following two inequalities hold simultaneously:

$$\begin{aligned}&{ \left| V_{[h^*_{i}, h^*_{j})}\right| \le \mu _{[h^*_{i}, h^*_{j})} +\sqrt{\frac{n \mu _{[h^*_{i}, h^*_{j})}}{{\delta }^{1-2{\alpha }}}}}; \ \ \text {and} \end{aligned}$$

(16)

$$\begin{aligned}&\left| Z_{[h^*_{i}, h^*_{j})}^B \right| { < 2}\mu _{[h^*_{i}, h^*_{j})} {\exp ({-{\delta }^{2{\alpha }}/4})}. \end{aligned}$$

(17)

In addition, if ${\delta }>\sqrt{n}$, with probability at least $1- 1/{n}$, $Z_{[0,2n)}^B = \emptyset$.

4.3 Step B

4.3.1 Preparations

Prior to performing Step B, we will expose that with high probability, all except a small fraction of vertices have relatively large degrees to S. We thus define below new types of bad vertices.

Definition 21

Let $Z_S$ be the set of vertices $v\in V(G)$ with less than ${s^*}\deg (v)/(2{\delta })$ neighbors in S. Let $Z^n_S\subset B$ be an arbitrary set of vertices such that each vertex $v \in Z_S$ has at least ${s^*}/2$ neighbors in $Z^n_S$ and $|Z^n_S| \le {\lceil {s^*}/2 \rceil } |Z_S|$.

To see that such set $Z^n_S$ exists, note that if a vertex has at most ${s^*}\deg (v)/(2{\delta })$ neighbors in S, then it has at least $\deg (v) - {s^*}\deg (v)/(2{\delta }) > {s^*}/2$ neighbors in B. For each $v \in Z_S$, we may thus choose arbitrary $\lceil {s^*}/2 \rceil$ neighbors of v in B and add these to $Z^n_S$. Consequently, $|Z^n_S| \le {\lceil {s^*}/2 \rceil } |Z_S|$. Note there might be vertices of $Z_S$ that are in S.

Lemma 22

With probability at least $1- \exp (-{s^*}/24)- 2\exp \left( - n/({4}\delta ^{0.5})\right)$, the following statements hold:

$$\begin{aligned}&\left| \left| S\right| - {s^*}n / {\delta }\right| \le n/\delta ^{0.5-\varepsilon }, \end{aligned}$$

(18)

$$\begin{aligned}&|Z_S| {<} 2ne^{-{s^*}/24}, \ \ \text {and thus} \ \ |Z^n_S| {<} {2} n {s^*}e^{-{s^*}/24}. \end{aligned}$$

(19)

In addition, if ${\delta }> \sqrt{n}$, with probability at least $1-1/{n}$, ${Z_S} = \emptyset$, and thus $Z^n_S= \emptyset$.

Proof

For each vertex v, let $Z_v= 1$ if v has less than ${s^*}\deg (v)/(2{\delta })$ neighbors in the random set S, and $Z_v=0$ otherwise. Thus $|Z_S|= \sum _v Z_v$.

Fix $v \in {V(G)}$; each of its $\deg (v)$ neighbors has independently probability ${s^*}/{\delta }$ to be in S. The expected number of neighbors of v in S is thus $\deg (v) {s^*}/{\delta }$. By the Chernoff Bound (Lemma 6),

$$\begin{aligned} \Pr (Z_v = 1)=&\Pr \left( \deg _S(v) { <} { 0.5}\mathbb {E}[\deg _S(v)] \right) \nonumber \\ \le&\Pr \left( \left| \deg _S(v) - \mathbb {E}[\deg _S(v)] \right| { >} 0.5 \mathbb {E}[\deg _S(v)] \right) \nonumber \\ \le&2\exp \left( - \mathbb {E}[\deg _S(v)]/12 \right) \nonumber \\ =&2\exp \left( - \deg (v){s^*}/(12{\delta }) \right) \le 2\exp \left( - {s^*}/12 \right) . \end{aligned}$$

(20)

Since $|Z_S|= \sum _v Z_v$, by (20) we have:

$$\begin{aligned} \mathbb {E}[|Z_S|] = \sum _v \Pr (Z_v=1) \le 2n\exp \left( - {s^*}/12 \right) . \nonumber \end{aligned}$$

Therefore, by Markov’s Inequality,

$$\begin{aligned} \Pr \left( |Z_S| \ge 2n\exp \left( - {s^*}/24 \right) \right) \le \mathbb {E}\left[ |Z_S|\right] / \left( 2n\exp \left( - {s^*}/24 \right) \right) \le \exp (-{s^*}/24). \end{aligned}$$

(21)

We are left to bound the probability that $\left| \left| S\right| - {s^*}n / {\delta }\right| \le n/\delta ^{0.5-\varepsilon }$. Each vertex independently has probability ${s^*}/{\delta }$ to be in S, and hence $\mathbb {E}[|S|]={s^*}n/{\delta }\ge n/\delta ^{0.5-\varepsilon }$. The Chernoff Bound thus implies that by (1),

$$\begin{aligned} \Pr \left( \left| \left| S\right| - {s^*}n / {\delta }\right| > n/\delta ^{0.5-\varepsilon }\right)\le & {} 2\exp \left( {-(n/\delta ^{0.5-\varepsilon })^2/(3{s^*}n/{\delta })}\right) \nonumber \\\le & {} { 2\exp \left( - n/({4}\delta ^{0.5-\varepsilon +\alpha }) \right) }\nonumber \\\le & {} 2\exp \left( - n/({4}\delta ^{0.5})\right) . \end{aligned}$$

(22)

Thus, by (21) and (22), with probability at least $1- 2\exp \left( - n/({4}\delta ^{0.5}) \right) - \exp (-{s^*}/24)$ the two desired statements (18) and (19) hold.

In addition, when ${\delta }> \sqrt{n}$, applying a union bound to (20) yields: $\Pr ({Z_S} = \emptyset ) \ge$ $1-n \cdot 2\exp (-{s^*}/12)> 1- 1/n$. $\square$

4.3.2 Weighting Step B

In this step we define a weight assignment $f_2: E(G) \rightarrow \mathbb {Z}$, with $\Vert f_2\Vert _\infty = o(n/{\delta })$, that is only supported on edges across B and modifies initial weights appointed by $f_1$. The goal is that at the end of Step B, the weights $(\tilde{f}_1 + \tilde{f}_2)(v)$ are distinct for vertices v in B (at least for these which are not bad), and the vertex weights in B are not equal to 0, 1, 2, 3, 4, 5 modulo k. Recall $k = \lceil k'/{ 1000} \rceil$. We may assume $k > 50$ (for sufficiently large ${\delta }$ and $n/{\delta }$).

Step 1. We first bound modifications necessary to set most vertex weights in B at values expected after Step A. We admit a small error though, as the expected values do not have to be integers.

Claim 23

We may construct $f_2: E(G) \rightarrow \mathbb {Z}$ supported on edges across $B {\setminus } \left( Z_{[0,{2}n)}^B \cup Z_S\right)$ and S so that

$$\begin{aligned} \Vert f_2\Vert _\infty \le { 2}\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) {\delta }^{1/2+{ \alpha }} /{s^*}+1~~~~~~ \textrm{and} ~~~~~~{ \left| (\tilde{f}_1+\tilde{f}_2)(v) - \sigma _\mu (v,Z(v))\right| \le 1} \end{aligned}$$

(23)

for each $v \in B \setminus \left( Z_{[0,{2}n)}^B \cup Z_S\right)$.

Proof

For each vertex $v \in B\setminus Z_{[0,{ 2}n)}^B$, by the definition of $Z_{h}^B$ (and (2)),

$$\begin{aligned} \left| \sigma (v,Z(v))- \sigma _\mu (v,Z(v))\right| \le \deg (v)^{1/2+{\alpha }} \left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) , \end{aligned}$$

(24)

i.e. the weight of v needs to be modified by at most $\deg (v)^{1/2+{\alpha }} \left( \lceil \frac{n}{{\delta }} \rceil +a'-1\right)$. If at the same time $v \notin Z_S$, then it has at least $\deg (v){s^*}/(2{\delta })$ neighbors in S. Therefore, by (24), in order to satisfy the second condition in (23), it is sufficient to modify each edge between $v\in B \setminus \left( Z_{[0,{2}n)}^B \cup Z_S\right)$ and its neighbors in S by at most

$$\begin{aligned}&\Bigg \lceil {\deg (v)^{1/2+{\alpha }} \left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'-1\right) / \deg _S(v)}\Bigg \rceil \nonumber \\&\quad < {\deg (v)^{1/2+{\alpha }} \left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) / (\deg (v){s^*}/(2{\delta }))} +1 \nonumber \\&\quad {=} {2}\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) {\delta }/({s^*}\deg (v)^{1/2-{\alpha }} ) + 1 \le {2}\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) {\delta }^{1/2+{\alpha }} /{s^*}+1. \end{aligned}$$

(25)

$\square$

Step 2 Now we wish to modify $f_2$ so that all the vertices in $B {\setminus } (Z_{[0,2n)}^B\cup Z_S)$ have distinct vertex weights under $\tilde{f}_1 + \tilde{f}_2$, while these weights are not equal to $0,1,\dots , 5$ modulo k.

Recall $v\in V_h$ means $\sigma _\mu (v, Z(v))\in I_h \subset [h(\lceil \frac{n}{{\delta }} \rceil +a'-1), (h+1)(\lceil \frac{n}{{\delta }} \rceil +a'-1))$.

Step 2-1 We first modify $f_2$ so that for $0 \le h < { 2}n$, all the vertices in every given $V_h \setminus (Z_{h}^B\cup Z_S)$ have distinct weights not equal to $0,1,\dots , 5$ modulo k, fitting as many as possible of these weights in $I_h$. (Note we will admit weights from different $V_h$’s to overlap for now.)

Let $\mathbb {Z}' \subset \mathbb {Z}$ be the set of integers which are not equal to 0 to 5 modulo k. Assume elements in $\mathbb {Z}'$ inherit their natural ordering from $\mathbb {Z}$. Two integers are said to be consecutive in $\mathbb {Z}'$ if they are consecutive in their ordering in $\mathbb {Z}'$. Intervals in $\mathbb {Z}'$ are thus consecutive integers in $\mathbb {Z}'$ with respect to the ordering in $\mathbb {Z}'$. For each interval I of consecutive |I| integers in $\mathbb {Z}$, it is easy to see that:

$$\begin{aligned} |I \cap \mathbb {Z}'| \ge (|I|-{ 6})(k-6)/k. \end{aligned}$$

(26)

By (26), the size of an interval $I \subset \mathbb {Z}$ does not change much after restricting it to $\mathbb {Z}'$, i.e.,

$$\begin{aligned} |I| \le |I \cap \mathbb {Z}'|k/(k-6)+{ 6}. \end{aligned}$$

(27)

Claim 24

For each integer $0 \le h < { 2}n$, it is sufficient to modify the weight of every $v\in V_h \setminus (Z_{h}^B\cup Z_S)$ by at most $\max (|V_h|, |I_h|)k/(k-6)+ { 12}$ in order to attribute distinct weights to all vertices in $V_h \setminus (Z_{h}^B\cup Z_S)$ and guarantee that these form consecutive integers in $\mathbb {Z}'$ with the smallest vertex weight equal to $\min (I_h\cap \mathbb {Z}')$, that is at most $h(\lceil n/{\delta } \rceil +a'-1)+6$.

Proof

For any given h, we analyze vertices in $V_h {\setminus } (Z_{h}^B\cup Z_S)$ one after another. By Claim 23, each such vertex v has the current weight at most one away from $\sigma _\mu (v,Z(v)) \in I_h$. Changing it by at most 7 we may thus shift this weight inwards $I_h\cap \mathbb {Z}'$. Next, in order to reach the least yet unoccupied position in $\mathbb {Z}'$ which is not smaller than $\min (I_h\cap \mathbb {Z}')$, this weight needs to be further shifted by at most $\max (|V_h|, |I_h|){ -1}$ consecutive integers in $\mathbb {Z}'$. Thus, by (27), the vertex weight of v after Step 1 needs to be changed in total by at most ${ 7 + ((} \max (|V_h|, |I_h|)k/(k-6)+ { 6)-1)}$. $\square$

Step 2-2 In this step we discuss further modifications of $f_2$, resulting in pairwise distinct weights from $\mathbb {Z}'$ associated to all vertices in $V_{[0, 2n)} \setminus (Z_{[0,2n)}^B\cup Z_S)$. We will need the following combinatorial lemma, concerning shifts of intervals sufficient to make them pairwise disjoint.

Lemma 25

Let p be a positive integer. For any p intervals ${I_i}=[a_i, b_i) \subset \mathbb {Z}$ (i.e., $a_i,b_i\in \mathbb {Z}$), $1\le i \le { p}$ where $a_1 \le a_2\le \dots \le a_{{ p}}$, there exist p disjoint intervals $I_i'\subset \mathbb {Z}$ with $I_i' = [a_i', b_i')$ such that $b_i'-a_i' = b_i - a_i$ for $1 \le i \le { p}$, $a_1=a_1' \le a_2' \le \dots \le a_{{ p}}'$ and

$$\begin{aligned} \max _{1\le i \le { p}} |a_i'-a_i| \le \max _{1\le l_1 < l_2 \le { p}-1} \left( \sum _{i=l_1}^{l_2} (b_i-a_i) - (a_{i+1}-a_{i}) \right) . \end{aligned}$$

(28)

Proof

As for any i, $|I_i'|=b_i' - a_i' = b_i-a_i = |I_i|$, an interval $I_i'$ may be regarded as the translation of $I_i$ by $a_i' - a_i$. We will prove the lemma by induction on p. For ${ p}=1$ the claim trivially holds.

Suppose ${ p} > 1$. First consider the case when $a_2 \ge b_1$, or equivalently $I_1$ is disjoint from $I_2$. By the inductive hypothesis applied to the intervals $I_2, \dots , I_{{ p}}$, we could shift them to disjoint intervals $I_2', \dots , I_{{ p}}'$ where $I_2$ is the same as $I_2'$. With $I_1$ having no need to shift, each of the remaining intervals has thus been shifted by at most $\max _{2\le l_1 < l_2 \le { p}-1} \left( \sum _{i=l_1}^{l_2} (b_i-a_i) - (a_{i+1}-a_{i}) \right)$. The shifted intervals $I_2', \dots , I_{{ p}}'$ are moreover still disjoint from $I_1$, since for $i\ge 2$, $a_i' \ge a_2' = a_2 \ge b_1$. Hence, the lemma holds.

We may thus assume that $a_2 < b_1$, i.e. $I_1$ and $I_2$ overlap. Since $I_1'$ needs to remain the same as $I_1$, the interval $I_2$ must shift to the right by (at least) $b_1 - a_2 = (b_1-a_1) - (a_2-a_1)$, and become $I_2' =[a_2', b_2')= [b_1, b_1+ |I_2|)=[b_1, b_1+ (b_2-a_2))$. If $I_2'$ is to the left of $I_3$ and $I_2'$ is disjoint from $I_3$ (i.e., $a_3 \ge b_2'$), by the inductive hypothesis applied to $I_3, \dots , I_{{ p}}$, we obtain a desired $\{I_i'\}_{1\le i\le { p}}$ with the maximum shift at most $\max \left( b_1-a_1- (a_2-a_1), \max _{3\le l_1 < l_2 \le { p}-1} \left( \sum _{i=l_1}^{l_2} (b_i-a_i) - (a_{i+1}-a_{i}) \right) \right)$, which is bounded above by the right-hand side in (28).

If on the other hand $I_2'$ overlaps with $I_3$ or $I_2'$ is to the right of $I_3$ (i.e., $a_3 < b_2'$), then $I_3$ has to be shifted, e.g. to $I_3' =[a_3', b_3')= [b_2', b_2'+ (b_3-a_3))$. We analogously continue this process, obtaining $I_j' = [a_j', b_j')$ sequentially for $j=3,\ldots ,l$ where ${ 3} \le l \le { p}$ is the last index such that $a_l < b_{l-1}'$. That is, for each $j\le l$, we set $a_j' = b_{j-1}'$, which is in fact the best we could do, and $b_j' = a_j'+ |I_j|= a_j'+ (b_j-a_j)$, thus $a_j' = a_1 + (b_1-a_1) + (b_2 - a_2) + \dots + (b_{j-1}-a_{j-1})$. Therefore, the shift of $I_j$ is $a_j' - a_j = a_1 + (b_1-a_1) + (b_2 - a_2) + \dots + (b_{j-1}-a_{j-1}) - a_j = \sum _{i=1}^{j-1} (b_i-a_i) { -} (a_{i+1}-a_i)$. Applying now the inductive hypothesis to $I_{l+1}, \dots , I_{{ p}}$, we obtain p intervals $I_1', \dots , I_{{ p}}'$ satisfying the conditions in the lemma, and with:

$$\begin{aligned}{} & {} \max _{1\le i \le { p}} |a_i'-a_i| \le \max \\{} & {} \quad \left( \max _{1\le j \le l-1} \sum _{i=1}^{j} (b_i-a_i) { -} (a_{i+1}-a_i), \max _{l+1\le l_1 < l_2 \le { p}-1} \left( \sum _{i=l_1}^{l_2} (b_i-a_i) - (a_{i+1}-a_{i}) \right) \right) , \end{aligned}$$

thus the lemma is proved. Furthermore, the upper bound is sharp when $l = { p}$. $\square$

Lemma 26

Assume (16) holds for all benchmarks $h^*_{i} { <} h^*_{j}$. Then, it is sufficient to further change the weight of each vertex in $V_{[0,{ 2}n)} {\setminus } (Z_{[0, { 2}n)}^B\cup Z_S)$ by at most $\frac{{ 3n}}{{\delta }^{1/2-{ \alpha }}}$ in order to shift them to pairwise distinct values in $\mathbb {Z}'$ (provided ${\delta }$ and $n/{\delta }$ are sufficiently large).

Proof

For each integer $0 \le h < 2n$, due to Claim 24, the weights of vertices in $V_h \setminus (Z_{[0,2n)}^B\cup Z_S)$ form an interval of length $|V_h \setminus (Z_{[0,2n)}^B\cup Z_S)|$ in $\mathbb {Z}'$ with the least element $a_h=\min (I_h\cap \mathbb {Z}')$. We now apply Lemma 25 to these intervals, taking into account only integers in $\mathbb {Z}'$, i.e., $(b_i-a_i)$ is evaluated as $|V_i {\setminus } (Z_{[0,2n)}^B\cup Z_S)|$ and $a_{i+1}-a_i$ is substituted by $|I_i \cap \mathbb {Z}'|$ in the lemma. Consequently, all the weights of vertices in $V_{[0,2n)} \setminus (Z_{[0,2n)}^B\cup Z_S)$ may remain in $\mathbb {Z}'$ and get pairwise distinct via shifting each of the vertex weights by at most the following number of consecutive integers in $\mathbb {Z}'$:

$$\begin{aligned}&\max _{{ 0}\le l_1< l_2 \le { 2n-2}} \left( \sum _{i=l_1}^{l_2} |V_i \setminus (Z_{[0,2n)}^B\cup Z_S)| - |I_i \cap \mathbb {Z}'| \right) \nonumber \\&\quad \le \max _{{ 0}\le l_1< l_2 \le { 2n-2}} \left( \sum _{i=l_1}^{l_2} |V_i| - |I_i \cap \mathbb {Z}'| \right) \nonumber \\&\quad \le \max _{{ 0}\le l_1< l_2 \le { 2n-2}} \left( \sum _{i=l_1}^{l_2} |V_i| - (|I_i|-{ 6}) (k-6)/k \right) \le \max _{{ 0}\le l_1 < l_2 \le { 2n-2}} \nonumber \\&\qquad \left( \sum _{i=l_1}^{l_2} \left( |V_i| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k \right) \right) , \end{aligned}$$

(29)

where the second inequality follows by (26) and the last inequality uses $|I_i| = \lceil n/{\delta } \rceil +a'-1$.

In order to upper-bound the quantity in (29), suppose the maximization is achieved when $l_1 = h_1$ and $l_2 = h_2$, and suppose $h_1$ is between benchmarks $h^*_{i-1}$ and $h^*_{i}$, i.e., $h^*_{i-1} { \le } h_1 { <} h^*_{i}$. Similarly, suppose $h^*_{j} \le h_2 < h^*_{j+1}$ for some $j\ge i-1$. Thus, the last quantity in (29) equals

$$\begin{aligned}&\sum _{h\in [h_1, h_2]} \left( |V_h| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\quad { \le } \sum _{h\in [h^*_{i}, h^*_{j})} \left( |V_h| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\qquad + \sum _{h\in [h^*_{j}, h_2+1)} \left( |V_h| - ( \Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\qquad + \sum _{h\in [h_1,h^*_{i})} \left( |V_h| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\quad \le \sum _{h\in [h^*_{i}, h^*_{j})} \left( |V_h| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\qquad + \sum _{h\in [h^*_{j}, h_2+1)} |V_h|+ \sum _{h\in [h_1,h^*_{i})} |V_h| \nonumber \\&\quad { \le } \sum _{h\in [h^*_{i}, h^*_{j})} \left( |V_h| - (\Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) (k-6)/k\right) \nonumber \\&\qquad + \sum _{h\in [h^*_{j}, h^*_{j+1})} |V_h|+ \sum _{h\in [h^*_{i-1},h^*_{i})} |V_h|. \end{aligned}$$

(30)

By (16) and (15) (implying that $\mu _{[h^*_{t}, h^*_{t+1})}\le { 2n/{\delta }}$ for every given t),

$$\begin{aligned}{} & {} \sum _{h\in [h^*_{j}, h^*_{j+1})} |V_h|+ \sum _{h\in [h^*_{i-1},h^*_{i})} |V_h| \le \mu _{[h^*_{i-1}, h^*_{i})} + \mu _{[h^*_{j}, h^*_{j+1})} \nonumber \\{} & {} \quad +\sqrt{\frac{n \mu _{[h^*_{i-1}, h^*_{i})}}{{\delta }^{1-2{ \alpha }}}} +\sqrt{\frac{n \mu _{[h^*_{j}, h^*_{j+1})}}{{\delta }^{1-2{ \alpha }}}} <3 n/{\delta }^{1-{ \alpha }}. \end{aligned}$$

(31)

Analogously, by (16) and the facts that $\mu _{[h^*_{i}, h^*_{j})} \le n$ and $\mu _h \le n/{\delta }$ for each h (due to Claim 15),

$$\begin{aligned} \sum _{h\in [h^*_{i}, h^*_{j})} |V_h| \le \mu _{[h^*_{i}, h^*_{j})} +\sqrt{\frac{n \mu _{[h^*_{i}, h^*_{j})}}{{\delta }^{1-2{ \alpha }}}} \le \frac{n(h^*_{j}-h^*_{i})}{{\delta }} + \frac{n}{{\delta }^{1/2-{ \alpha }}}. \end{aligned}$$

(32)

By (31) and (32), the last quantity in  (30) is thus bounded above by

$$\begin{aligned}&\frac{n(h^*_{j}-h^*_{i})}{{\delta }} + \frac{{ n}}{{\delta }^{1/2-{ \alpha }}} - (h^*_{j}-h^*_{i})( \Bigg \lceil {n/{\delta }}\Bigg \rceil +a'-{ 7}) \frac{k-6}{k} + \frac{3n}{{\delta }^{1-{ \alpha }}} \nonumber \\&\quad \le \frac{n(h^*_{j}-h^*_{i})}{{\delta }} + \frac{{ n}}{{\delta }^{1/2-{ \alpha }}}- (h^*_{j}-h^*_{i})\frac{n}{{\delta }}\frac{k-6}{k} - (h^*_{j}-h^*_{i})(a'-{ 7})\frac{k-6}{k} + \frac{3n}{{\delta }^{1-{ \alpha }}} \nonumber \\&\quad = \frac{n(h^*_{j}-h^*_{i})}{{\delta }} + \frac{{ n}}{{\delta }^{1/2-{ \alpha }}} - (h^*_{j}-h^*_{i})\frac{n}{{\delta }} + (h^*_{j}-h^*_{i})\frac{n}{{\delta }}\frac{6}{k}\nonumber \\&\qquad - (h^*_{j}-h^*_{i})(a'-{ 7})\frac{k-6}{k} + \frac{3n}{{\delta }^{1-{ \alpha }}} \nonumber \\&\quad = \frac{{ n}}{{\delta }^{1/2-{ \alpha }}}+ (h^*_{j}-h^*_{i}) \left( \frac{n}{{\delta }}\frac{6}{k} - (a'-{ 7})\frac{k-6}{k} \right) + \frac{3n}{{\delta }^{1-{ \alpha }}} \nonumber \\&\quad \le \frac{{ n}}{{\delta }^{1/2-{ \alpha }}} + \frac{3n}{{\delta }^{1-{ \alpha }}} < \frac{{ 2n}}{{\delta }^{1/2-{ \alpha }}} . \end{aligned}$$

The second to last inequality above holds because by the definitions of k and $a'$,

$$\begin{aligned}\frac{n}{{\delta }}\frac{6}{k} - (a'-{ 7})\frac{k-6}{k} \le 0\end{aligned}$$

for $\delta$ and $n/\delta$ (thus also k) large enough. We have thus proved that each vertex needs to shift its weight by at most $\frac{{ 2n}}{{\delta }^{1/2-{ \alpha }}}$ consecutive integers in $\mathbb {Z}'$. Hence, by (27), each vertex needs to shift its weight by at most $\left( \left( \frac{{ 2n}}{{\delta }^{1/2-{ \alpha }}} { +1}\right) \frac{k}{k-6}+{ 6}\right) { -1} < \frac{{ 3n}}{{\delta }^{1/2-{ \alpha }}}$ (in $\mathbb {Z}$). $\square$

4.3.3 Summary of Step B

Corollary 27

Assume (16) holds for all benchmarks $h^*_{i} < h^*_{j}$. Then, the following can be achieved (for $\delta$ and $n/\delta$ large enough).

Vertices v in $B {\setminus } \left( Z_{[0,{ 2}n)}^B \cup Z_S\right)$ can be provided distinct weights in $\mathbb {Z}'$ due to appropriately chosen $f_2$ supported on edges across $B {\setminus } \left( Z_{[0,{ 2}n)}^B \cup Z_S\right)$ and S, with $\Vert f_2\Vert _\infty \le \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2$.

Consequently, each edge e in E(B) satisfies $(f_1+f_2)(e) = 1$ or $\lceil n/{\delta } \rceil +a'$, while each edge e between B and $S_q$, for $1\le q \le k'$, satisfies

$$\begin{aligned} (f_1+f_2)(e)\in & {} \left[ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k' +q)- \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) ,\right. \nonumber \\{} & {} \left. \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q)+ \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) \right] . \end{aligned}$$

(33)

Proof

Claim 23 within Step 1 shows we may first modify weights of edges across B and S by at most ${ 2}\left( \lceil \frac{n}{{\delta }} \rceil +a'\right) {\delta }^{1/2+{ \alpha }} /{s^*}+1$ so that for each $v \in B {\setminus } \left( Z_{[0,{ 2}n)}^B \cup Z_S\right)$, $(\tilde{f}_1+\tilde{f}_2)(v)$ is at most one away from $\sigma _\mu (v,Z(v))$.

In Step 2-1, Claim 24 exposes that the weight of each vertex $v\in V_h {\setminus } (Z_{h}^B\cup Z_S)\subseteq V_{[h^*_{i}, h^*_{i+1})}$ (for any given h, i) needs to further change by at most $\max (|V_h|, |I_h|)k/(k-6)+ { 12}$ to be shifted to $\mathbb {Z}'$ and get distinguished from the remaining ones in $V_h {\setminus } (Z_{h}^B\cup Z_S)$. By (16) and (15), we have $|V_h| \le \mu _{[h^*_{i}, h^*_{i+1})} +\sqrt{\frac{n \mu _{[h^*_{i}, h^*_{i+1})}}{{\delta }^{1-2{ \alpha }}}} \le { 2n/{\delta }} + { \sqrt{2}}n/{\delta }^{1-{ \alpha }} < { 1.5} n/{\delta }^{1-{ \alpha }}$. We also have $|I_h| = \lceil n/{\delta } \rceil +a'-1 < { 1.5} n/{\delta }^{1-{ \alpha }}$. Thus the weight of v needs to shift by at most $( { 1.5} n/{\delta }^{1-{ \alpha }}) \cdot k/(k-6)+ { 12} < { 2}n/{\delta }^{1-{ \alpha }}$ within this step.

Finally, within Step 2-2, by Lemma 26, the vertices in $V_{[0,{ 2}n)} \setminus (Z_{[0, { 2}n)}^B\cup Z_S)$ need to change their weights by at most ${ 3}n/{\delta }^{1/2-{ \alpha }}$ to make them pairwise distinct and keep them in $\mathbb {Z}'$.

Steps 2-1 and 2-2 together require changing vertex weights by at most ${ 2}n/{\delta }^{1-{ \alpha }} + { 3}n/{\delta }^{1/2-{ \alpha }} < { 3.5}n/{\delta }^{1/2-{ \alpha }}$. Since $v \notin Z_S$, it has at least ${s^*}/2$ neighbors in S. Therefore, we only need to modify the weight of each edge between v and S by at most $\lceil ({ 3.5}n/{\delta }^{1/2-{ \alpha }}) /({s^*}/2) \rceil < { 7}n/{\delta }^{1+\varepsilon }+1$ in Step 2.

In Steps 1 and 2 combined, the weight of each edge across $B {\setminus } \left( Z_{[0,{ 2}n)}^B \cup Z_S\right)$ and S is thus changed by at most

$$\begin{aligned} { 2}\left( \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil +a'\right) \frac{{\delta }^{\frac{1}{2}+{ \alpha }}}{{s^*}} +1 + \frac{{ 7}n}{{\delta }^{1+\varepsilon }}+1 < { 4}\left( {\frac{n}{{\delta }}}\right) \frac{{\delta }^{\frac{1}{2}+{ \alpha }}}{{s^*}} +1 + \frac{{ 7}n}{{\delta }^{1+\varepsilon }}+1 { \le } \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2. \end{aligned}$$

The lemma is thus proved, as its last statement follows by the definition of $f_1$ in Step A. $\square$

4.4 Preparations to Step C

We define the last set of bad vertices.

Definition 28

For each integer $1 \le q \le k'$, let $Z_{S_{q}}$ be the set of vertices v in $S_q$ such that $\left| \deg _B(v) - \deg (v)({\delta }-{s^*})/{\delta }\right| {>} \deg (v)^{1/2+\varepsilon }$.

Lemma 29

With probability at least $1 - k'e^{-{\delta }^{2\varepsilon }/6}$, for all $1 \le q \le k'$,

$$\begin{aligned}&|Z_{S_{q}}| {<} \frac{4n{s^*}}{{\delta }k'} \exp (-{\delta }^{2\varepsilon }/6). \end{aligned}$$

(34)

In addition, when ${\delta }> \sqrt{n}$, with probability at least $1- 1/{n}$, $\bigcup _{1\le q \le k'} Z_{S_{q}} = \emptyset$.

Proof

Consider any fixed integer $q\in [1,k']$. For each vertex v, let $Z_v$ be the indicator random variable that $v \in S_q$ but $\left| \deg _B(v) - \deg (v)({\delta }-{s^*})/{\delta }\right|$ ${>} \deg (v)^{1/2+\varepsilon }$. Thus, $|Z_{S_{q}}| = \sum _v Z_v$. For each vertex v,

$$\begin{aligned} \Pr (Z_v = 1) = \Pr \left( v\in S_q\right) \Pr \left( \left| \deg _B(v) - \deg (v)({\delta }-{s^*})/{\delta }\right| {>} \deg (v)^{1/2+\varepsilon } \,\Big \vert \, v\in S_q \right) . \end{aligned}$$

Each neighbor of v is placed in B independently with probability $({\delta }-{s^*})/{\delta }$, and thus $\mathbb {E}[\deg _B(v)]= \deg (v)({\delta }-{s^*})/{\delta }$, which is greater than $\deg (v)^{1/2+\varepsilon }$. Thus, by the Chernoff Bound,

$$\begin{aligned} \Pr \left( \left| \deg _B(v) - \deg (v)\frac{{\delta }-{s^*}}{{\delta }} \right| {>} \deg (v)^{1/2+\varepsilon } \,\Big \vert \, v\in S_q \right)&\le 2\exp \left( - \frac{\deg (v)^{1+2\varepsilon }}{3\deg (v)\frac{{\delta }-{s^*}}{{\delta }}}\right) \nonumber \\&< 2e^{-{\delta }^{2\varepsilon }/3}. \end{aligned}$$

(35)

Therefore,

$$\begin{aligned} \mathbb {E}[|Z_{S_{q}}|]{} & {} =\mathbb {E}\left[ \sum _v Z_v\right] { = \sum _v \Pr (Z_v = 1)} \le \sum _v \Pr (v\in S_q)\cdot 2\exp (-{\delta }^{2\varepsilon }/3)\nonumber \\{} & {} \quad < \frac{2n{s^*}}{{\delta }k'}\cdot 2\exp (-{\delta }^{2\varepsilon }/3). \end{aligned}$$

(36)

By Markov’s Inequality and (36),

$$\begin{aligned} \Pr \left( |Z_{S_{q}}| \ge \frac{2n{s^*}}{{\delta }k'}\cdot 2\exp (-{\delta }^{2\varepsilon }/6)\right)\le & {} \mathbb {E}[|Z_{S_{q}}|]/\left( \frac{2n{s^*}}{{\delta }k'}\cdot 2\exp (-{\delta }^{2\varepsilon }/6)\right) \\\le & {} \exp (-{\delta }^{2\varepsilon }/6), \end{aligned}$$

and therefore, (34) holds by a union bound for $1 \le q \le k'$.

In addition, when ${\delta }> \sqrt{n}$, by a union bound over v and q on (35), with probability at least $1-nk' 2e^{-{\delta }^{2\varepsilon }/3} > 1-1/{ n}$, $Z_{S_{q}} = \emptyset$ for all $1 \le q \le k'$. $\square$

So far we have obtained the following sets of bad vertices, which require different treatments in Step C:

• 1. the set $Z_{[0,2n)}^B \subset B$, whose weights in Step A are not close to the expected values,

• 2. the set $Z_S$, whose degrees to S are less than ${s^*}{ \deg (v)}/(2{\delta })$,

• 3. a set $Z^n_S\subset B$, which are neighbors of vertices in $Z_S$ such that each vertex in $Z_S$ has at least ${s^*}/2$ neighbors in $Z^n_S$, and lastly,

• 4. the sets $Z_{S_{q}} \subset S_q$, $1\le q \le k'$ of vertices whose degrees to B are far from expected.

Definition 30

Denote by $U_{\textrm{b}}$ the union of all these four types of bad vertices. The complement of $U_{\textrm{b}}$ in S will in turn be referred to as the set of good vertices and denoted $U_{\textrm{g}}$, $U_{\textrm{g}}=S {\setminus } U_{\textrm{b}}\subset S$.

Claim 31

With probability at least $1- { 2}e^{-n/({ 4}{\delta }^{0.5})} - ({ 8}{\delta }^2)e^{-\frac{1}{{ 3}}\sqrt{\frac{n}{{\delta }^{1-2{ \alpha }}}}} - { 5{\delta }^2} e^{-{\delta }^{{ 2}{ \alpha }}/{ 4}}$,

$$\begin{aligned}|U_{\textrm{b}}| < { 3}{ n}e^{{-{\delta }^{ { 2}{ \alpha }}/ { 4}}} \end{aligned}$$

(provided ${\delta }$ and $n/{\delta }$ are sufficiently large). Furthermore, if ${\delta }> \sqrt{n}$, then with probability at least $1- { 3}/{ n}$, $U_{\textrm{b}}= \emptyset$.

Proof

By Corollary 20, Lemmas 22 and 29,

$$\begin{aligned} |U_{\textrm{b}}| {<}&|Z_{[0,{ 2}n)}^B| + |Z_S| + |Z^n_S| + \left( \sum _{q=1}^{k'} |Z_{S_{q}}| \right) \\ \le&{ 2}n e^{{-{\delta }^{{ 2}{ \alpha }}/{ 4}}} + 2ne^{-{s^*}/24} +{ 2}n {s^*}e^{-{s^*}/24} + k' \frac{4n{s^*}}{{\delta }k'} e^{-{\delta }^{2\varepsilon }/6} < { 3}{ n}e^{{-{\delta }^{ { 2}{ \alpha }}/ { 4}}} \end{aligned}$$

with probability at least $1 - { 4}{\delta }^2e^{-{\delta }^{{ 2}{ \alpha }}/{ 4}} - ({ 8}{\delta }^2)e^{-\frac{1}{{ 3}}\sqrt{\frac{n}{{\delta }^{1-2{ \alpha }}}}} - e^{-{s^*}/24} - 2e^{- n/({ 4}\delta ^{0.5})} - k'e^{-{\delta }^{2\varepsilon }/6} > 1- { 2}e^{-n/({ 4}{\delta }^{0.5})} - ({ 8}{\delta }^2)e^{-\frac{1}{{ 3}}\sqrt{\frac{n}{{\delta }^{1-2{ \alpha }}}}} - { 5{\delta }^2} e^{-{\delta }^{{2}{ \alpha }}/{ 4}}$.

In addition, when ${\delta }> \sqrt{n}$, again by Corollary 20, Lemmas 22 and 29, with probability at least $1- { 3}/{ n}$, $U_{\textrm{b}}= \emptyset$. $\square$

We will further refer to two vertices in S as being “close” (Definition 32) if their vertex weights could potentially be very close in terms of values after Step C. We will make sure vertices which are “close”do not have the same vertex weight after Step C. Informally, $u \in L(v)$ if u, v are “close”, whereas for $u \notin L(v)$ we will prove later that the weights of u, v cannot be the same after Step C.

Definition 32

For any two vertices $v, u\in S$, we say $u\in L(v)$ and $v \in L(u)$ if there are integers $1 \le p, q \le k'$ such that $v\in S_q$, $u \in S_p$ and both of the following two conditions hold:

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) \nonumber \\&\quad > \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+p) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (u); \end{aligned}$$

(37)

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) \nonumber \\&\quad < \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+p) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (u). \end{aligned}$$

(38)

Lemma 33

With probability at least $1- { 2n} \exp \left( - \frac{1}{3}{\frac{{s^*}n}{{\delta }k'}}\right)$ (if $n/{\delta }$ and ${\delta }$ are large enough), for every $v \in S$,

$$\begin{aligned} |L(v)| \le 2{ \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }}}. \end{aligned}$$

Proof

Suppose (37) holds. Note $\lceil \lceil n/{\delta } \rceil /(3k') \rceil (k'+q) \le \lceil \lceil n/{\delta } \rceil /(3k') \rceil (k'+k')< (((n/{\delta })+1)/(3k')+1)2k' = { 2n/(3{\delta }) + 2/3 + 2k' < 0.99 n/{\delta }}$. Therefore, the left hand side of (37) equals at most $(n/{\delta }) \deg (v)$. Analogously, the right hand side of (37) equals at least $\left( n/(3{\delta }) - n/(6{\delta })\right) \deg (u) = \deg (u)n/(6{\delta })$. Therefore, (37) implies: $(n/{\delta }) \deg (v) > \deg (u)n/(6{\delta })$, i.e., $6\deg (v) > \deg (u).$ Similarly, (38) implies $6\deg (u) > \deg (v).$ Therefore, if $u\in L(v)$, then

$$\begin{aligned} 1/6< \deg (v)/\deg (u)< 6. \end{aligned}$$

(39)

Given $v\in S_q$ for some fixed $1\le q \le k'$, we compute the probability that |L(v)| is large. To this end we first show that for a given vertex $u\in V(G)\setminus \{v\}$, if it satisfies both (37) and (38), then there is only one $S_p$ with $1\le p \le k'$ that u can be placed in. Rearranging inequality (37), we obtain

$$\begin{aligned} k'+p < \frac{\left( \Bigg \lceil {\Bigg \lceil {n/{\delta }}\Bigg \rceil /(3k')}\Bigg \rceil (k'+q) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \frac{\deg (v)}{\deg (u)} + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) }{\Bigg \lceil {\Bigg \lceil {n/{\delta }}\Bigg \rceil /(3k')}\Bigg \rceil }. \end{aligned}$$

Similarly, by (38),

$$\begin{aligned} k'+p > \frac{\left( \Bigg \lceil {\Bigg \lceil {n/{\delta }}\Bigg \rceil /(3k')}\Bigg \rceil (k'+q) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \frac{\deg (v)}{\deg (u)} - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) }{\Bigg \lceil {\Bigg \lceil {n/{\delta }}\Bigg \rceil /(3k')}\Bigg \rceil }. \end{aligned}$$

These two inequalities mean that if $u \in L(v)$, then by (39), $k'+{ p}$ must belong to an interval in $\mathbb {R}$ of length at most

$$\begin{aligned}&2\left( \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \cdot 6 +\left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) / \Bigg \lceil {\Bigg \lceil {n/{\delta }}\Bigg \rceil /(3k')}\Bigg \rceil \\&\quad< 14 \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) / (n/(3{\delta }k'))< { \frac{{ 546} k'}{{\delta }^{\varepsilon }} + \frac{168 k' {\delta }}{n} < 1}. \end{aligned}$$

Therefore, there indeed may be at most one p so that $u \in S_{{ p}}$ implies $u \in L(v)$. Thus,

$$\begin{aligned} \Pr \left( u \in L(v) { \,\big \vert \, v \in S_q } \right) \le { \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{1}{{\delta }}}. \nonumber \end{aligned}$$

Hence, the expected number of vertices u such that $u \in L(v)$ given $v\in S_q$ equals at most ${ \lceil {s^*}/k' \rceil (n-1)/{\delta }< \lceil {s^*}/k' \rceil n/{\delta }}$. Since for fixed v and q such that $v\in S_q$, the events $u \in L(v)$ are independent for all $u{ \ne v}$, by the Chernoff Bound we thus obtain that:

$$\begin{aligned} { \Pr \left( |L(v)| - \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }} > \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }} \,\Big \vert \, v \in S_q \right) }&{ \le 2 \exp \left( -\frac{1}{3} \left( \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }}\right) \right) }\\ {\le }&2 \exp \left( -\frac{1}{3} \left( {\frac{{s^*}n}{{\delta }k'}}\right) \right) . \end{aligned}$$

Therefore, by the law of total probability, for any given $v\in V(G)$, ${ \Pr \left( |L(v)| > 2\lceil \frac{{s^*}}{k'} \rceil \frac{n}{{\delta }} \,\Big \vert \, v \in S \right) }$ ${ \le }$ ${ 2 \exp \left( -\frac{1}{3} \left( {\frac{{s^*}n}{{\delta }k'}}\right) \right) .}$ Hence,

$$\begin{aligned}&{ \Pr \left( \left( v \in S\right) \Rightarrow \left( |L(v)| \le 2\Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }} \right) \right) ~ } { =} { ~1- \Pr \left( \left( v \in S\right) \wedge \left( |L(v)|> 2 \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }} \right) \right) }\\&\qquad { \ge } { ~1- \Pr \left( |L(v)| > 2\Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }} \,\Big \vert \, v \in S \right) \ge 1- 2 \exp \left( -\frac{1}{3} \left( {\frac{{s^*}n}{{\delta }k'}}\right) \right) .} \end{aligned}$$

By a union bound over all vertices v we thus obtain the thesis. $\square$

Corollary 34

With positive probability, all the following inequalities hold (for ${\delta }$ and $n/{\delta }$ sufficiently large):

$$\begin{aligned}&|U_{\textrm{b}}|< { 3} { n}\exp ({-{\delta }^{ { 2}{ \alpha }}}/ { 4}) , \\&|S| \in [{s^*}n/{\delta }- n/\delta ^{0.5-\varepsilon }, {s^*}n/{\delta }+ n/\delta ^{0.5-\varepsilon }], \\&|L(v)| \le 2{ \Bigg \lceil {\frac{{s^*}}{k'}}\Bigg \rceil \frac{n}{{\delta }}} \text { for all } v\in S.\\&{ \left| V_{[h^*_{i}, h^*_{j})}\right| \le \mu _{[h^*_{i}, h^*_{j})} +\sqrt{\frac{n \mu _{[h^*_{i}, h^*_{j})}}{{\delta }^{1-2{ \alpha }}}}} \text { for any two benchmarks } h^*_{i}{ <} h^*_{j}. \end{aligned}$$

In addition, when ${\delta }> \sqrt{n}$, then $U_{\textrm{b}}= \emptyset$.

Proof

This corollary is an immediate consequence of Corollary 20, Lemma 22, Claim 31 and Lemma 33, as $1-{ 4}{\delta }^2 { e^{-{\delta }^{2{ \alpha }}/4}} - { 8}{\delta }^2\exp \left( -\frac{1}{{ 3}}\sqrt{\frac{n}{{\delta }^{1-2{ \alpha }}}}\right) - e^{-{s^*}/24} - 2e^{- n/({ 4}\delta ^{0.5})} - { 2}e^{-n/({ 4}{\delta }^{0.5})} - { 8}{\delta }^2\exp \left( -\frac{1}{{ 3}}\sqrt{\frac{n}{{\delta }^{1-2{ \alpha }}}}\right) - { 5{\delta }^2} e^{-{\delta }^{{ 2}{ \alpha }}/{ 4}} - { 2n} \exp \left( - \frac{1}{3}{\frac{{s^*}n}{{\delta }k'}}\right) -\frac{{ 3}}{{ n}} > 0$ when ${\delta }$ is sufficiently large. $\square$

4.5 Step C

Throughout Step C, we assume the statements in Corollary 34 hold.

4.5.1 Goal

Definition 35

Let $G'$ be the graph on the vertex set $U_{\textrm{b}}\cup S$ whose edges consist of all the edges in G[S], all the edges between $U_{\textrm{b}}$ and S in G and all the edges between $Z_S$ and $Z^n_S\subset B$ in G.

Note that by the definitions of $G'$, $Z_S$ and $Z^n_S$, for every $v\in V(G')$,

$$\begin{aligned} \deg _{G'}(v)\ge \frac{{s^*}}{2}. \end{aligned}$$

(40)

In this step we will only change the weights of edges in $G'$. Our goal is to obtain pairwise distinct weights in $\mathbb {Z}\setminus \mathbb {Z}'$ (i.e., equal to $0,1, \dots , 5$ modulo k) for all vertices in $V(G') = U_{\textrm{b}}\cup S$ after Step C. Within it we will not change the weights of edges incident to vertices in $B \setminus U_{\textrm{b}}$. Therefore, the weights of vertices in $B \setminus U_{\textrm{b}}$ will remain distinct and in $\mathbb {Z}'$ by Steps A and B (Corollary 27).

4.5.2 Step C-1

Initialization We initialize Step C by assigning to all edges in $G'[S]=G[S]$ and $G'[B]$ the new weight: $\lceil \lceil \frac{n}{{\delta }} \rceil /2 \rceil$. We do not modify the weights of edges across B and S in $G'$ yet, though.

Suppose $C_1, \dots , C_T$ are the non-trivial connected components in $G'[S]$ (i.e., of order larger than one), ordered arbitrarily. Let W be the set of isolated vertices in $G'[S]$. Clearly, $W \subset Z_S\subset U_{\textrm{b}}$ by the definitions of $Z_S$ and $U_{\textrm{b}}$. Set

$$\begin{aligned}U': = V(G') \setminus (S\setminus W).\end{aligned}$$

Claim 36

We may modify every edge weight in $G'$ by at most 2 so that each vertex weight in $U'$ equals 0 or 1 modulo k, each vertex weight in $U_{\textrm{g}}\setminus U'$ equals 2 or 3 modulo k and each vertex weight in $U_{\textrm{b}}\setminus U'$ equals 4 or 5 modulo k.

Proof

We will apply an algorithm analogous to the ones used in [25, 30], whose origins date back to [39].

Given an arbitrary ordering $v_1, v_2, \dots , v_{|S \cup U_{\textrm{b}}|}$ of vertices in $G'$, each edge $\{v_i, v_j\}$ with $i<j$ is called a forward edge of $v_i$ and a backward edge of $v_j$. For each $v \in U'$, define a set $\mathcal {A}_{v} = \{0,1\}$. For each $v \in U_{\textrm{g}}\setminus U'$, define $\mathcal {A}_{v} =\{2,3\}$. Finally, for each $v \in U_{\textrm{b}}\setminus U'$, set $\mathcal {A}_{v} =\{4,5\}$. For $i = 1, 2, \dots$, we consider each consecutive $v_i$ after another and modify weights of edges incident with $v_i$ in $G'$ so that the weight of $v_i$ lands in $\mathcal {A}_{v}$ modulo k. We also guarantee that this weight does not leave $\mathcal {A}_{v}$ (modulo k) throughout the further part of the algorithm.

By (40), the first vertex $v_1$ has at least ${s^*}/2$ neighbors, i.e., at least ${s^*}/2$ forward edges in $G'$. We modify each forward edge of $v_1$ by adding 0 or 1 to its weight. Thereby, we may obtain at least ${ {s^*}/2}{ +1} { > k + 6}$ distinct weights which are consecutive integers for $v_1$. Thus, there is a way of choosing these modifications so that the weight of $v_1$ belongs to $\mathcal {A}_{v}$ modulo k.

We then proceed consecutively with $v_i$, $i=2,3,\ldots$. For a given i, we again admit adding 0 or 1 to the weights of the forward edges of $v_i$. There are two admissible modifications for the weights of backward edges of $v_i$ as well. These belong to the set $\{-1,0,1\}$. Specifically, say $\{v_i,u\}$ is a backward edge of $v_i$. If the vertex weight of u modulo k is currently the smaller value in $\mathcal {A}_{u}$, then we admit modifying the weight of $\{v_i,u\}$ by adding 0 or 1. Note that this in particular guarantees that the updated vertex weight of u will remain in $\mathcal {A}_{u}$ modulo k. By the same reason, we admit adding 0 or $-1$ to the weight of $\{v_i,u\}$ if the vertex weight of u modulo k is currently the larger value in $\mathcal {A}_{u}$.

Consequently, analogously as for $v_1$, we may thereby obtain at least $\deg _{G'}(v) { +1} \ge {s^*}/2 { +1} > k+6$ weights which are consecutive integers for $v_i$. Thus, there is a way of choosing these modifications so that the weight of $v_i$ belongs to $\mathcal {A}_{v}$ modulo k, which is our goal.

Since each edge in $G'$ can be modified at most twice: once as a forward edge and once as a backward edge, each edge in $G'$ changes its weight by at most 2 in Step C-1. $\square$

4.5.3 Step C-2

Step C-2 is more technical. We in particular handle all bad vertices within it. Given an ordering $v_1, \dots , v_{|S\cup U_{\textrm{b}}|}$ of vertices in $G'$ (specified later), again each edge $\{v_i, v_j\}$ with $i<j$ is called a forward edge of $v_i$ and a backward edge of $v_j$. We will again use an algorithm inspired by [25, 30, 39].

If $v_i \in U_{\textrm{b}}$, we say all its forward and backward edges are active. If $v_i\in U_{\textrm{g}}$, then only its forward and backward edges in E(S) are called active. (Note that a good vertex v in S could be adjacent to some vertex u in $U_{\textrm{b}}\setminus S$. Such an edge would still be active for $u\in U_{\textrm{b}}$, but would not be active for $v\in U_{\textrm{g}}$.) We call a vertex terminal if it has no active forward edge in the ordering.

Recall that by the definitions in Step C-1, the non-trivial components in $G'[S]$: $C_1,\dots , C_T$ together with the set W of isolated vertices in S partition S. Furthermore, as $W \subset Z_S\subset U_{\textrm{b}}$, by Corollary 34, $|W| \le |U_{\textrm{b}}| < |S|$. Thus, there is at least one nontrivial connected component in $G'[S]$. Recall

$$\begin{aligned}V(G') = S\cup U_{\textrm{b}}, \ \ \ U' = V(G') \setminus (C_1 \cup \dots \cup C_T).\end{aligned}$$

The following properties of $G'$ are immediate from the definitions of different types of bad vertices and $G'$.

Claim 37

Each vertex in $G'$ has at least ${s^*}/2$ active edges in $G'$,

$$\begin{aligned} U' \subset U_{\textrm{b}}, \ \ U_{\textrm{g}}\subset S \setminus U', \ \ V(G') = U'\cup S. \end{aligned}$$

(41)

Thus, in particular, if $v \in V(G')$ is a good vertex, then its neighbors in $G'$ which are not in S are bad vertices.

Ordering of Vertices We now specify the ordering of the vertices in $G'$. Let $t_i, i=1,2,\dots$ denote the terminal vertices in the ordering. For each i, let $r_i$ be the vertex immediately preceding $t_i$ in the ordering. We show there is an ordering satisfying the following claim.

Claim 38

There is an ordering of the vertices in $G'$ such that all vertices in $U'$ come before vertices not in $U'$. Furthermore, the ordering satisfies the following conditions.

• 1. For each i, $\{r_i, t_i\}$ is always an edge in $G'$ and moreover, this edge is an active forward edge for $r_i$.

• 2. The vertex sets $\{r_i, t_i\}_i$ are pairwise disjoint.

• 3. For each i, the pair $\{r_i, t_i\}$ satisfies one of the following: either both $t_i, r_i$ are in $U' \subset U_{\textrm{b}}$, or both $t_i, r_i$ are in $S \setminus U'$.

Proof

Let $C_1', \dots , C_{T'}'$ be the non-trivial connected components in $G'[U']$. Suppose $W'$ is the set of isolated vertices in $G'[U']$.

We order the vertices in $G'$ as follows: we start from the vertices in $W'$, ordered arbitrarily. Coming next will be the vertices in $C_1', \dots , C_{T'}'$, sequentially. Last in the ordering will in turn be vertices in $C_1, \dots , C_T$, sequentially. Note that we have not specified the ordering within each $C_i$ or $C_i'$ yet. Nevertheless, it is already clear that vertices in $U'$ will all come before vertices not in $U'$ in the ordering. (See Fig. 1).

Fig. 1

Illustration of ordering of vertices in $V(G')$. Black vertices are good vertices in S; gray vertices are bad vertices in S, and white vertices are bad vertices in $U'\setminus S$.

We finally specify the ordering within non-trivial connected components $C_i$, $C_i'$. To this end we simply use reversed BFS to order the vertices in each of these, one after another. Consequently, if r, t are the last two vertices in the ordering in a given such component, then t is the root of the corresponding BFS tree, and hence $\{r, { t}\}\in E(G')$.

Consider a given $C_i'$, $1\le i \le T'$. Since all the vertices in $C_i'$ are bad, in particular the last two vertices r, t in $C_i'$ are bad vertices in $U'$, hence, $\{r,t\}$ is an active forward edge for r. Analogously, for a given $C_i$, $1\le i\le T$, all vertices in $C_i$ are in $S\setminus U'$ and, in particular, so are the last two vertices r, t in $C_i$. Moreover, since all edges in $C_i \subset S$ are active, the edge $\{r, { t}\}$ is an active forward edge for r. Additionally, by the definition of BFS, only the last vertex (i.e., the root t) can be a terminal vertex in any given $C_i'$ or $C_i$.

We are left to show that there is no terminal vertex in $W'$. Since the minimum degree of $G'$ is at least ${s^*}/2$ and $W'$ itself is an independent set in $G'$, each vertex in $W'$ has at least ${s^*}/2$ incident edges joining it with vertices in $V(G')\setminus W'$, which come after $W'$ in the ordering. Since $W' \subset U_{\textrm{b}}$, these forward edges are active. Therefore vertices in $W'$ cannot be terminal. $\square$

Anchor sets Let   ${ t^{\textrm{b}}= \lceil { 48}ne^{-{\delta }^{2{ \alpha }}/{ 4}}/{s^*} \rceil },~~ { t^{\textrm{g}}= { 2}\lceil \frac{{ 16}n}{{\delta }k'}\frac{1}{t^{\textrm{b}}} \rceil t^{\textrm{b}}}$. In particular,   $({2}t^{\textrm{b}}) \mid t^{\textrm{g}}$.

Each vertex in $G'$ is either in $U'$, and thus is a bad vertex, or is in $S\setminus U'$, and thus could either be good or bad.

Each bad vertex $v\in U'$ will be assigned in step C-2 an anchor set $\overline{\mathcal{A}\mathcal{P}}_v$ of two elements of the following form: $\{l+ (2\lambda ) t^{\textrm{b}}k+ak, l+ (2\lambda +1) t^{\textrm{b}}k+ak\}$, where $\lambda \ge 0$ and $a\in [0,t^{\textrm{b}}-1]$ are integers to be determined in Step C-2, and $l = 0$ or 1 is the weight of v modulo k at the end of Step C-1, and thus is pre-determined. All the elements in $\overline{\mathcal{A}\mathcal{P}}_v$ are regarded modulo $t^{\textrm{g}}k$. For a fixed $l = 0$ or 1, by varying $\lambda$ and a, these sets partition the set of integers $\{l+k\cdot \mathbb {Z}\}$ modulo $t^{\textrm{g}}k$. Different values of a correspond to different congruence classes modulo $t^{\textrm{b}}k$, denoted by $\overline{\mathcal {C}}_a(l) = \{l+ ak+ t^{\textrm{b}}k \cdot \mathbb {Z}\mod t^{\textrm{g}}k\}$. Note these are well defined, as $t^{\textrm{g}}$ is divisible by $t^{\textrm{b}}$.

Similarly, each vertex $v\in V(G')\setminus U'$ will be assigned in step C-2 a set $\mathcal{A}\mathcal{P}_v$ of the form $\{l+ (2\lambda ) t^{\textrm{g}}k+ak, l+ (2\lambda +1) t^{\textrm{g}}k+ak\} \subset \mathbb {Z}_{\ge 0}$, where $\lambda , a$ are integers with $\lambda \ge 0$, $a\in [0,{ t^{\textrm{g}}}-1]$ to be determined in Step C-2, and $l = 2,3,4$, or 5 is the vertex weight of v modulo k at the end of Step C-1. For a fixed l, these sets partition the set of non-negative integers $\{l+k\cdot \mathbb {Z}_{\ge 0} \}$. Different values of a correspond to different congruence classes, denoted by ${\mathcal {C}}_a(l) = \{l+ak+ t^{\textrm{g}}k \cdot \mathbb {Z}\}$.

Goal For $i = 1, 2, \dots$, the algorithm sequentially analyzes each $v_i$, greedily modifying weights of active edges incident to $v_i$ in $G'$ in order to prescribe the vertex weight of $v_i$ to an appropriately chosen set ${\overline{\mathcal{A}\mathcal{P}}_{v_i}}$ (if $v_i \in U'$) or ${\mathcal{A}\mathcal{P}_{v_i}}$ (if $v_i \notin U'$), described above. Furthermore:

• (i) In the process of analyzing a given $v_j$, for any $i<j$, the set $\mathcal{A}\mathcal{P}_{v_i}$ or $\overline{\mathcal{A}\mathcal{P}}_{v_i}$ remains unchanged. That is, the vertex weight of $v_i$ stays in $\mathcal{A}\mathcal{P}_{v_i}$ if $v_i\notin U'$, and stays in $\overline{\mathcal{A}\mathcal{P}}_{v_i}$ modulo $t^{\textrm{g}}k$ if $v_i\in U'$ throughout this and all later stages of the algorithm.

• (ii) The bad vertices in $U' = U_{\textrm{b}}\cap U'$ have distinct $\overline{\mathcal{A}\mathcal{P}}_{v}$’s (modulo $t^{\textrm{g}}k$) assigned, with vertex weights being 0 or 1 modulo k.

• (iii) The bad vertices in $U_{\textrm{b}}\setminus U'$ have distinct $\mathcal{A}\mathcal{P}_{v}$’s assigned, with vertex weights being 4 or 5 modulo k.

• (iv) Each good vertex $v\in U_{\textrm{g}}\setminus U' = U_{\textrm{g}}$ has assigned a set $\mathcal{A}\mathcal{P}_{v}$ different from the ones of vertices in L(v), with vertex weights being 2 or 3 modulo k.

Rules Rules of modifying edge weights are as follows. Suppose we are analyzing $v_i$ and $\{u, v_i\}$ is an edge incident to $v_i$ in $G'$.

• 1. For $v_1$, let $\mathcal{A}\mathcal{P}_{v_1}$ (if $v_1 \notin U'$) or $\overline{\mathcal{A}\mathcal{P}}_{v_1}$ (if $v_1 \in U'$) be the set of the desired form that contains the current vertex weight of $v_1$ (modulo $t^{\textrm{g}}k$, if $v_1\in U'$). Note the current weight of $v_1$ uniquely determines the set $\mathcal{A}\mathcal{P}_{v_1}$ or $\overline{\mathcal{A}\mathcal{P}}_{v_1}$, respectively. We next move to $v_2$.

• 2. Only the active backward and forward edges of $v_i$ can get weights changed.

• 3. To modify an active forward edge $\{v_i, u\}$ of $v_i$, we admit adding to its weight an integer in $\{0,k, 2k,\dots t^{\textrm{b}}k\}$ if $v_i \in U_{\textrm{b}}\cap U' = U'$, and respectively, an integer in $\{0,k, 2k,\dots t^{\textrm{g}}k\}$ if $v_i \notin U'$. The forward edges of $v_i$ will together account for the congruence class $\overline{\mathcal {C}}_a(l)$, if $v_i \in U'$, or ${\mathcal {C}}_a(l)$, if $v_i \notin U'$, the weight of $v_i$ will ultimately belong to.

• 4. There are two options to modify each active backward edge $\{v_i, u\}$ of $v_i$ if both $v_i, u \in S\setminus U'$. We admit to modify the weight of $\{v_i,u\}$ by adding 0 or $t^{\textrm{g}}k$ if the current weight of u is the smaller value in $\mathcal{A}\mathcal{P}_u$, and adding 0 or $-t^{\textrm{g}}k$ if the current weight of u is the larger value in $\mathcal{A}\mathcal{P}_u$.

• 5. There are two options to modify each active backward edge $\{v_i, u\}$ of $v_i$ if both $v_i, u \in U'$. We admit to modify the weight of $\{v_i,u\}$ by adding 0 or $t^{\textrm{b}}k$ if the current weight of u is congruent to the element $l + (2\lambda )t^{\textrm{b}}k + ak$ in $\overline{\mathcal{A}\mathcal{P}}_u$, and adding 0 or $-t^{\textrm{b}}k$ if the current weight of u is congruent to the element $l + (2\lambda +1)t^{\textrm{b}}k + ak$ in $\overline{\mathcal{A}\mathcal{P}}_u$ modulo $t^{\textrm{g}}k$.

• 6. If $v_i\in U'$ but $u \notin U'$, since all vertices in $U'$ come before vertices not in $U'$ (by Claim 38), $\{v_i, u\}$ cannot be a backward edge of $v_i$. Follow Rule 3 to modify this edge as an active forward edge of $v_i$.

• 7. If $v_i\notin U'$ but $u \in U'$, there are two options to modify each active backward edge $\{v_i, u\}$. We admit to modify the weight of $\{v_i,u\}$ by adding 0 or $t^{\textrm{g}}k$. Note however that if $v_i \in U_{\textrm{g}}$ and $u \in U' {\setminus } S$, then $\{v_i, u\}$ is not an active backward edge of $v_i$, by the definition of active edges for good vertices.

Claim 39

The Rules above guarantee Goal (i) holds throughout the algorithm.

Proof

It is easy to see from Rules 4–6 that the updated weight of u remains in $\mathcal{A}\mathcal{P}_u$ or $\overline{\mathcal{A}\mathcal{P}}_u$, respectively, even after changing the weight of an active backward edge $\{v_i, u\}$ of $v_i$. Since $\overline{\mathcal{A}\mathcal{P}}_u$’s are regarded modulo $t^{\textrm{g}}k$, Rule 7 also guarantees that the updated weight of u stays in $\overline{\mathcal{A}\mathcal{P}}_u$. $\square$

Claim 40

Assume (16) holds for all benchmarks $h^*_{i} < h^*_{j}$.

After Step C-2, each edge of G[S] has weight in $[\lceil \lceil n/{\delta } \rceil /2 \rceil -2t^{\textrm{g}}k-2, \lceil \lceil n/{\delta } \rceil /2 \rceil +2t^{\textrm{g}}k+2]$ and each edge of $G'[B]$ has weight in $[\lceil \lceil n/{\delta } \rceil /2 \rceil -2t^{\textrm{b}}k-2, \lceil \lceil n/{\delta } \rceil /2 \rceil +2t^{\textrm{b}}k+2]$. During Step C, each edge across $U'{\setminus } S$ and $U_{\textrm{g}}$ changes its weight by at most $t^{\textrm{b}}k + 2$ and each edge across $U' {\setminus } S$ and $S {\setminus } U_{\textrm{g}}$ changes its weight by at most $t^{\textrm{g}}k + t^{\textrm{b}}k + 2$. Edges not in $G'$ do not get weights changed.

However, if $U_{\textrm{b}}= \emptyset$, then $G' = G[S]$ and $U' =\emptyset$. After Step C-2, each edge of G[B] has then weight 1 or $\lceil n/{\delta } \rceil +a'$ and each edge in G[S] has weight in $[\lceil \lceil n/{\delta } \rceil /2 \rceil -2t^{\textrm{g}}k-2, \lceil \lceil n/{\delta } \rceil /2 \rceil +2t^{\textrm{g}}k+2]$. Moreover, during Step C, no weights are changed for edges across B and S.

Proof

Each edge can be modified at most twice in Step C-2: once as an active forward edge and once as an active backward edge. By the Rules above, each time its weight is modified, it can be changed by at most $t^{\textrm{g}}k$. Thus each edge weight can be changed in total by at most $2t^{\textrm{g}}k$ in Step C-2. Step C-1 changes in turn an edge weight by at most 2 by Claim 36. Since at the beginning of Step C-1, each edge weight in E(S) was initialized as $\lceil \lceil n/{\delta } \rceil /2 \rceil$, the result for edges in E(S) follows.

For each edge in $E(G') \cap E(B)$, both its ends are bad vertices, and thus Step C-1 changes its weight by at most 2 and Step C-2 changes its weight by at most $2t^{\textrm{b}}k$, by Rules 3 and 5. The result follows, since the edge weight was initialized as $\lceil \lceil n/{\delta } \rceil /2 \rceil$ at the beginning of Step C-1.

For each edge between $v\in U_{\textrm{g}}$ and $u\in { U'}{\setminus } S$, again Step C-1 changes its weight by at most 2. Vertex u must be a bad vertex and it comes before v in the ordering. In Step C-2, while analyzing u, the weight of $\{v, u\}$ is changed by at most $t^{\textrm{b}}k$, by Rule 3. In the process of analyzing v in turn, since $v \in U_{\textrm{g}}$ but $u \notin S$, the edge $\{v, u\}$ is not active for v, by the definition of active edges for good vertices, and thus could not be changed. The result follows.

For each edge between $v\in S{\setminus } U_{\textrm{g}}$ and $u\in { U'}{\setminus } S$, v is either in $U'$ or not. If $v \in U'$, then since $u\in U'$, Step C-2 changes the weight of $\{u, v\}$ by at most $2t^{\textrm{b}}k$, by Rules 3 and 5. If $v \notin U'$, then v comes after u in the ordering. In Step C-2, the weight of $\{u,v\}$, being an active forward edge of u, is thus changed by at most $t^{\textrm{b}}k$, and, as an active backward edge of v, changed by at most $t^{\textrm{g}}k$, due to Rules 3 and 7. The result follows analogously as above, as $t^{\textrm{g}}> t^{\textrm{b}}$.

The case when $U_{\textrm{b}}= \emptyset$ follows from Corollary 27, by noting that $V(G') = S$ and $U'\subset U_{\textrm{b}}=\emptyset$, by Claim 37, and thus Step C does not change weights of edges in E(B) or edges across B and S. $\square$

Lemma 41

Suppose all the inequalities in Corollary 34 hold. There is a way to modify the edge weights abiding the Rules of the algorithm so that Goals (i)–(iv) are fulfilled.

Proof

Goal (i) is fulfilled by Claim 39. By the Rules, all edge weights in $G'$ are changed in Step C-2 by multiples of k. Thus, the modulo k conditions in Goals (ii) to (iv) automatically hold by the preparatory measures from Step C-1 (Claim 36). It remains to show that we can process the vertices $v_i$ for $i = 1,2,\dots$, complying with the Rules, so that the rest of the conditions in Goals (ii) to (iv) hold.

Suppose we are analyzing a given $v_i$ which is not a terminal vertex nor a vertex immediately preceding a terminal vertex. Suppose at the end of Step C-1 the weight of $v_i$ equals $l_i$ modulo k.

Case 1. Suppose $v_i \in U'$. We first choose any of its active forward edges, say e. Due to adding to its weight admissible values in the set $\{0, k, 2k, \dots , t^{\textrm{b}}k\}$ (Rule 3), the weight of $v_i$ runs through all the congruence classes $\overline{\mathcal {C}}_a(l_i)$ with $0 \le a \le t^{\textrm{b}}-1$. The sets $\overline{\mathcal{A}\mathcal{P}}_{u}$ fixed already for $u \in U'$ prior to $v_i$ occupy at most $|U'| \le |U_{\textrm{b}}|$ congruence classes $\overline{\mathcal {C}}_a(l_i)$, with possible duplicates. By an averaging argument, there must be an $a^*$ such that at most $|U_{\textrm{b}}|/t^{\textrm{b}}$ of these sets $\overline{\mathcal{A}\mathcal{P}}_u$ are in the same congruence class $\overline{\mathcal {C}}_{a^*}(l_i)$. Fix such a congruence class $\overline{\mathcal {C}}_{a^*}(l_i)$ and assure the weight of $v_i$ belongs in it via adjusting the weight of e. We then modify the rest of the active forward edges of $v_i$ by adding 0 or $t^{\textrm{b}}k$ to their weights, and modify the weights of its active backward edges by 0 or $\pm t^{\textrm{b}}k$, according to Rules 5 and 6. Since $v_i$ is incident to at least ${s^*}/2$ active edges in $G'$ (by Claim 37), the vertex weight of $v_i$ can thus be attributed at least $\min (t^{\textrm{g}}/ t^{\textrm{b}}, { {s^*}/2})$ consecutive terms in the set $\{l_i+a^*k + t^{\textrm{b}}k\cdot \mathbb {Z}\mod t^{\textrm{g}}k\}=\overline{\mathcal {C}}_{a^*}(l_i)$. Since each of the at most $|U_{\textrm{b}}|/t^{\textrm{b}}$ existing sets $\overline{\mathcal{A}\mathcal{P}}_u$ in $\overline{\mathcal {C}}_{a^*}(l_i)$ blocks two consecutive terms in $\overline{\mathcal {C}}_{a^*}(l_i)$, we can find an achievable ${ \overline{\mathcal{A}\mathcal{P}}}_{v_i} \subset \overline{\mathcal {C}}_{a^*}(l_i)$ that is disjoint from all the prior $\overline{\mathcal{A}\mathcal{P}}_u$ (modulo $t^{\textrm{g}}k$) with $u \in { U'}$ if

$$\begin{aligned} { \min (t^{\textrm{g}}/ t^{\textrm{b}},} { {s^*}/2} { ) >} { 2|U_{\textrm{b}}|/t^{\textrm{b}}. } \end{aligned}$$

Since we assumed inequalities in Corollary 34 hold, $|U_{\textrm{b}}| \le { 3} { n \exp (-\delta ^{2{ \alpha }}/{ 4})}$, and thus:

$$\begin{aligned} { \min (t^{\textrm{g}}/t^{\textrm{b}},} { {s^*}/2} { ) > 4|U_{\textrm{b}}|/t^{\textrm{b}}+ 2.} \end{aligned}$$

(42)

Therefore we are done with $v_i$.

Case 2. Suppose $v_i \notin U'$. The analysis is almost the same as in Case 1. Suppose $v_i$ is a good vertex. By an averaging argument, there must be an $a^*$ such that the congruence class ${\mathcal {C}}_{a^*}(l_i)$ hosts at most $|L(v_i)|/t^{\textrm{g}}$ prior sets $\mathcal{A}\mathcal{P}_u$ with $u \in L(v_i)$. We insert the weight of $v_i$ in this congruence class via modifying one of its active forward edges, by adding to its weight one of the admissible integers in $\{0, k, 2k, \dots , t^{\textrm{g}}k\}$. We then modify the weights of the rest of the active edges of $v_i$ by an integer in $\{0, \pm t^{\textrm{g}}k\}$ abiding the Rules. Since $v_i$ is incident to at least ${s^*}/2$ active edges in $G'$ (by Claim 37), the vertex weight of $v_i$ can thereby be attributed at least ${s^*}/2$ consecutive terms in ${\mathcal {C}}_{a^*}(l_i) = \{l_i+a^*k + t^{\textrm{g}}k\cdot \mathbb {Z}\}$. Since each of the at most $|L(v_i)|/t^{\textrm{g}}$ existing sets $\mathcal{A}\mathcal{P}_u$ in ${\mathcal {C}}_{a^*}(l_i)$ and with $u\in L(v_i)$ blocks two consecutive terms in ${\mathcal {C}}_{a^*}(l_i)$, we can find an achievable $\mathcal{A}\mathcal{P}_{v_i} \subset {\mathcal {C}}_{a^*}(l_i)$ that is disjoint from all the prior $\mathcal{A}\mathcal{P}_u$ with $u \in L(v_i)$ if

$$\begin{aligned} { {s^*}/2} { > } { 2|L(v_i)|/t^{\textrm{g}}. } \nonumber \end{aligned}$$

Thus we are done with $v_i$ by the bound $|L(v)| \le 2{ \lceil {s^*}/k' \rceil (n/{\delta })}$ in Corollary 34, which holds for every $v\in S$, and implies in particular that:

$$\begin{aligned} { {s^*}/2} { > } { 4}{ |L(v)|/t^{\textrm{g}}+ 2. } \end{aligned}$$

(43)

The case when $v_i \notin U'$ and $v_i \in U_{\textrm{b}}$ follows by the same argument, with $L(v_i)$ replaced by $U_{\textrm{b}}\setminus U'$. Thus we are done with $v_i$ if only

$$\begin{aligned} { {s^*}/2} { >} { 2|U_{\textrm{b}}|/t^{\textrm{g}}} { \ge } { 2|U_{\textrm{b}}\setminus U'|/t^{\textrm{g}}. } \end{aligned}$$

The first inequality above follows however by (42), as $t^{\textrm{g}}> t^{\textrm{b}}$, while the second one trivially holds.

We are left to show how to manage $r_i, t_i$, where $t_i$ is a terminal vertex and $r_i$ is the vertex preceding $t_i$ in the ordering. We apply a similar approach as above, analyzing the both vertices simultaneously. By Claim 38, $\{ r_i, t_i\}$ is an edge in $G'$, which is an active forward edge for $r_i$.

Case 1’. Suppose both $r_i, t_i$ are in $U'$. Thus the both vertices are bad vertices. By an averaging argument, when we reach $r_i$, we can modify its forward edge $\{r_i, t_i\}$ so that the two new congruence classes of $r_i, t_i$ each hosts at most $2|U'|/t^{\textrm{b}}\le 2|U_{\textrm{b}}|/t^{\textrm{b}}$ prior sets $\overline{\mathcal{A}\mathcal{P}}_u$ with $u\in U'$, ignoring temporarily $r_i$ from the point of view of $t_i$. Fix such two new congruence classes for $r_i, t_i$ by choosing an admissible modification for the edge $\{r_i, t_i\}$. By the same argument as before, since ${ \min (t^{\textrm{g}}/t^{\textrm{b}},} { {s^*}/2}{ ) > 4|U_{\textrm{b}}|/t^{\textrm{b}}+2}$ (where “$+2$” might be necessary to adjust the weight of $t_i$ in the case when it belongs to the same congruence class as $r_i$), which holds by (42), via changing the weights of active backward edges of $r_i$ and all its other active forward edges except $\{r_i, t_i\}$ by values in $\{0, \pm t^{\textrm{b}}k\}$ complying with the Rules, there is an achievable choice of $\overline{\mathcal{A}\mathcal{P}}_{r_i}$ that is disjoint from all the sets $\overline{\mathcal{A}\mathcal{P}}_u$ for $u\in U'$ prior to $r_i$. Next, via changing the weights of the active backward edges of $t_i$ except $\{r_i, t_i\}$ by values in $\{0, \pm t^{\textrm{b}}k\}$ complying with the Rules, and by (42) again, we can find an achievable $\overline{\mathcal{A}\mathcal{P}}_{t_i}$ that is disjoint from all the prior sets $\overline{\mathcal{A}\mathcal{P}}_u$ with $u\in U'$ including $\overline{\mathcal{A}\mathcal{P}}_{r_i}$.

Case 2’. Suppose neither $r_i$ nor $t_i$ are in $U'$, i.e., $r_i, t_i \in S{\setminus } U'$. If both $r_i, t_i$ are bad vertices, we carry out the same reasoning as in Case 1’ with $t^{\textrm{b}}$ replaced by $t^{\textrm{g}}$. The inequality we need to guarantee in such a case is ${ {s^*}/2}{ > 4|U_{\textrm{b}}|/t^{\textrm{g}}+2,}$ which holds by (42). If both $r_i$ and $t_i$ are good vertices, again we use the same reasoning as in Case 1’, with $|U_{\textrm{b}}|$ replaced by $\max (|L(r_i)|, |L(t_i)|)$ and $t^{\textrm{b}}$ replaced by $t^{\textrm{g}}$. The inequality we need to guarantee this time is:

$$\begin{aligned}{ {s^*}/2} { > 4\max (|L(r_i)|, |L(t_i)|)/t^{\textrm{g}}+2}, \end{aligned}$$

which holds by (43). If finally one of $r_i, t_i$ is good and the other one is bad, say among $\{r_i, t_i\}$, u is the bad vertex and v is the good one, by modifying the active forward edge $\{r_i, t_i\}$, we may assure each of the weights of $t_i$ and $r_i$ to be in a congruence class containing at most $(|L(v)|+|U_{\textrm{b}}\setminus U'|) /t^{\textrm{g}}\le (|L(v)|+|U_{\textrm{b}}|)/t^{\textrm{g}}$ prior sets $\mathcal{A}\mathcal{P}_{v'}$ with $v' \in L(v)$ (in the case of v) and $\mathcal{A}\mathcal{P}_{u'}$ with $u' \in U_{\textrm{b}}{\setminus } U'$ (in the case of u). Fix such a congruence class by choosing an appropriate admissible weight for $\{r_i, t_i\}$. By changing the weights of the remaining active edges of v by values in $\{0, \pm t^{\textrm{g}}k\}$ complying with the Rules, we can find an achievable $\mathcal{A}\mathcal{P}_v$ that is disjoint from all $\mathcal{A}\mathcal{P}_{v'}$ with $v' \in L(v)$ prior to v if

$$\begin{aligned} { {s^*}/2} > { 2(|L(v)|+|U_{\textrm{b}}|)/t^{\textrm{g}}}. \end{aligned}$$

The inequality holds by  (42) and (43), and thus v can be successfully processed. To adjust the weight of the bad vertex u, we analogously as above change the weights of active edges of u except the edge $\{u,v\} = \{r_i, t_i\}$ by values in $\{0, \pm t^{\textrm{g}}k\}$ complying with the Rules. By the same argument as for v, we can find an achievable set $\mathcal{A}\mathcal{P}_u$ that is disjoint from the ones of the other prior bad vertices not in $U'$ if ${ {s^*}/2} > { 2}(|L(v)|+|U_{\textrm{b}}|)/t^{\textrm{g}},$ which again holds by  (42) and (43). This finishes the proof by the third condition in Claim 38. $\square$

4.6 Proof of Theorems 4 and 5

Lemma 42

Assume all statements in Corollary 34 hold. Then, for any two good vertices u, v with $u \notin L(v)$, the weights of v and u are distinct after Step C provided that ${\delta }$ and $n/{\delta }$ are sufficiently large.

Proof

Suppose $v \in S_q{ \cap U_{\textrm{g}}}$ for some $1\le q \le k'$. By Corollary 27, prior to Step C, the weight of any edge e between v and its neighbor in B is in the interval

$$\begin{aligned} \left[ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) ,\ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q)+ \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) \right] . \end{aligned}$$

Let $x= 1$ if $U_{\textrm{b}}\ne \emptyset$ and $x= 0$ if $U_{\textrm{b}}= \emptyset$. By Claim 40, since $v\in U_{\textrm{g}}$, the weight of an edge e between v and B is changed by at most $x(t^{\textrm{b}}k +2)$ during Step C. Thus the final weight of e is in the interval

$$\begin{aligned}{} & {} \left[ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }} + xt^{\textrm{b}}k +2x+2\right) ,\ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q)\right. \\{} & {} \quad + \left. \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+ xt^{\textrm{b}}k +2x+2\right) \right] . \end{aligned}$$

Since ${ t^{\textrm{b}}= \lceil { 48}ne^{-{\delta }^{2{ \alpha }}/{ 4}}/{s^*} \rceil }$, if ${\delta }\le \sqrt{n}$ and ${\delta }$ is sufficiently large, then $n/{\delta }^{1+\varepsilon } >t^{\textrm{b}}k$. If ${\delta }> \sqrt{n}$ in turn, then by the last statement in Corollary 34, $U_{\textrm{b}}= \emptyset$, and hence $x=0$. Thus, the weight of e is in any case in the interval

$$\begin{aligned} \left[ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) ,\ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q)+ \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }}+4 \right) \right] . \end{aligned}$$

Therefore, the weight of v coming from its neighbors in B equals at least

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg _B(v). \end{aligned}$$

(44)

Similarly, the weight of v coming from its neighbors in B equals at most

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg _B(v). \end{aligned}$$

(45)

Note that by definition, for large enough $\delta$ and $n/\delta$, $k< k'/960 < 10^{-5}n/\delta$, and thus

$$\begin{aligned}&t^{\textrm{g}}k< \frac{32 n}{\delta k'}k+2t^{\textrm{b}}k< \frac{1}{30}\frac{n}{\delta } +\frac{96ne^{-\delta ^{2\alpha }/4}k}{\delta ^{1/2+\varepsilon +\alpha }} +2 k < \frac{1}{20}\frac{n}{\delta } . \end{aligned}$$

(46)

Therefore, by (46) and Claim 40, weights of edges in E(S) are contained in the interval

$$\begin{aligned} \left[ \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{2}}\Bigg \rceil -2t^{\textrm{g}}k-2, \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{2}}\Bigg \rceil +2t^{\textrm{g}}k+2\right] \subset [1, { n/{\delta }}). \end{aligned}$$

(47)

Since v is a good vertex, by the definition of $Z_{S_{q}}$,

$$\begin{aligned} |\deg _B(v) - { \deg (v)({\delta }-{s^*})}/{\delta }| { \le } \deg (v)^{1/2+\varepsilon }, \end{aligned}$$

(48)

and thus,

$$\begin{aligned} |\deg _S(v) - \deg (v){s^*}/{\delta }| { \le } \deg (v)^{1/2+\varepsilon }. \end{aligned}$$

(49)

By (44), (47), and (48), we conclude that for $\delta$ and $n/\delta$ large enough, the weight of v equals at least

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg _B(v) + 0 \cdot \deg _S(v) \nonumber \\&\quad \ge \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \left( \frac{\deg (v)({\delta }-{s^*})}{{\delta }} - \deg (v)^{1/2+\varepsilon }\right) \nonumber \\&\quad \ge \deg (v)\left( 1- \frac{{s^*}}{{\delta }}- \frac{1}{{\delta }^{1/2-\varepsilon }} \right) \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \nonumber \\&\quad> \deg (v)\left( 1- \frac{2{s^*}}{{\delta }} \right) \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} +4 \right) \right) \nonumber \\&\quad> \deg (v)\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) - \frac{2{s^*}}{{\delta }}\frac{n}{{\delta }}\right) \nonumber \\&\quad > \deg (v)\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) , \end{aligned}$$

(50)

where the last inequality follows by (1). Similarly, by (45), (47) and (49), when ${\delta }$ and $n/{\delta }$ are sufficiently large, the weight of v equals at most

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg _B(v) + \deg _S(v){ \frac{n}{{\delta }}}\nonumber \\&\quad \le \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) + \left( \deg (v)\frac{{s^*}}{{\delta }}+\deg (v)^{1/2+\varepsilon }\right) { \frac{n}{{\delta }}}\nonumber \\&\quad \le \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) + \deg (v)\left( \frac{{s^*}}{{\delta }} + \frac{1}{{\delta }^{1/2-\varepsilon }}\right) { \frac{n}{{\delta }}}\nonumber \\&\quad< \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 12}n}{{\delta }^{1+\varepsilon }} + 4 \right) + \frac{2{s^*}}{{\delta }}{ \frac{n}{{\delta }}} \right) \deg (v)\nonumber \\&\quad < \left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v), \end{aligned}$$

(51)

where the last inequality again follows by (1). Therefore, (50) and (51) provide the lower and upper bounds on the weight of $v\in S_q \cap U_{\textrm{g}}$ after Step C. Analogous bounds hold also by the same reasoning for any $u\in S_p \cap U_{\textrm{g}}$, where $1\le p, q \le k'$. Thus, if the weights of v and u are equal after Step C, both of the following two inequalities must hold:

$$\begin{aligned}&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) >\\&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+p) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4\right) \right) \deg (u); \\&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+q) - \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (v) <\\&\left( \Bigg \lceil {\Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil \frac{1}{3k'}}\Bigg \rceil (k'+p) + \left( \frac{{ 13}n}{{\delta }^{1+\varepsilon }} + 4 \right) \right) \deg (u). \end{aligned}$$

These two conditions are equivalent to $u\in L(v)$ and $v\in L(u)$, cf. Definition 32. Therefore, if $u\notin L(v)$, then the weights of u and v cannot be the same after Step C. $\square$

We are finally ready to argument that Theorem 4 indeed holds.

If ${\delta }$ or $n/{\delta }$ are small, say ${\delta }< { c}$ or $n/{\delta }< { c}$ for some absolute constant c, we make use of the result in [25]. This implies that $s(G) \le (n/{\delta })(1+ 5) + 6$, and therefore $s(G) \le \frac{n}{{\delta }} + 5{ c} + 6$ in the case when $n/{\delta }<{ c}$, and $s(G) \le \frac{n}{{\delta }}\left( 1 + \frac{5{ c}^{\varepsilon }}{{\delta }^{\varepsilon }}\right) + 6$ in the case when ${\delta }<{ c}$.

From now on we can assume that ${\delta }$ and $n/{\delta }$ are sufficiently large. Thus, with positive probability, all the inequalities in Corollary 34 hold. In particular, $U_{\textrm{b}}= \emptyset$ if ${\delta }> \sqrt{n}$. We first show that all the vertex weights are distinct after Step C. Most vertices in B receive distinct weights in $\mathbb {Z}'$ within Step B, cf. Corollary 27. The remaining ones are distinguished in Step C by means of weights outside $\mathbb {Z}'$. By Lemma 41, Goals (i) to (iv) can be achieved in Step C. By the Goals, it is clear that all the vertex weights are distinct, with the only possible exception between vertices $v \in U_{\textrm{g}}$ and good vertices not in L(v). However, Lemma 42 shows that if $u \notin L(v)$, then the weights of u, v cannot be identical. Thus we have shown that all vertices in G indeed have distinct weights.

We next bound the values of the final edge weights after Step C. By Claim 40, the fact that $t^{\textrm{g}}{ >} t^{\textrm{b}}$, and (47), weights of edges in G[S] and $G'[B]$ are contained in $[1, { n/{\delta }})$. Other edges in B but not in $G'$ do not get weights changed during Step C (by Claim 40). Thus, by Corollary 27, these edges in B have weights either 1 or $\lceil n/{\delta } \rceil +a'$. As for the edges across B and S, prior to Step C, by (33) in Corollary 27, their weights were in the interval $\left[ \lceil \lceil \frac{n}{{\delta }} \rceil \frac{1}{3k'} \rceil k'- \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) ,\lceil \lceil \frac{n}{{\delta }} \rceil \frac{1}{3k'} \rceil 2k'+ \left( \frac{{ 11}n}{{\delta }^{1+\varepsilon }}+2\right) \right] \subset \left[ \frac{n}{{ 4}{\delta }}, \frac{3n}{4{\delta }} \right]$ after Step B. During Step C, by Claim 40 again, their weights are changed by at most $t^{\textrm{g}}k + t^{\textrm{b}}k + 2 { < \frac{n}{4\delta }}$, by (46). Thus, after Step C, the weights between B and S lie in the interval $[1, n/{\delta }).$ Consequently, we have shown that all final edge weights are positive, with the maximum weight at most

$$\begin{aligned} \Bigg \lceil {n/{\delta }}\Bigg \rceil +a' \le \Bigg \lceil {\frac{n}{{\delta }}}\Bigg \rceil + \Bigg \lceil {\frac{{ 7} n}{{ {\delta }}k}}\Bigg \rceil . \end{aligned}$$

By our choice of k, Theorem 4 holds, i.e. there are absolute constants $c_1, c_2$ (for any fixed $\varepsilon \in (0, 0.25)$) such that $s(G)\le \frac{n}{\delta }+\frac{c_1n}{\delta ^{1+\varepsilon }}+c_2$. To see why Theorem 5 holds, note that when ${\delta }^{1+\varepsilon } { \ge } n$, then $\frac{c_1n}{\delta ^{1+\varepsilon }}$ is upper bounded by $c_1$.

5 Conclusion

In this paper, we proved a uniform upper bound $s(G) \le \frac{n}{{\delta }}(1+c_1/{\delta }^{\varepsilon }) + c_2$, where $c_1, c_2$ are absolute constants for any $\varepsilon \in (0, 0.25)$. This confirms the Faudree-Lehel Conjecture for ${\delta }\ge n^{1/(1+\varepsilon )}$. We did not strive to optimize all the constants in our result. We believe that with a slightly modified construction one should be in particular able to magnify the 0.25 upper bound on $\varepsilon$. Our bound matches the bound in Conjecture 2 asymptotically when $\delta$ is large. It would also be interesting to prove a bound of the form $s(G) \le \frac{n}{{\delta }}(1+o_n(1)) + c$ for some absolute constant c.