Neighbor Sum Distinguishing Index of Graphs with Maximum Average Degree

Xizhao Sun

Department of Mathematics, Zhejiang Normal University, Jinhua, China.

DOI: 10.4236/jamp.2021.910161                

Abstract

A proper k-edge coloring of a graph G = (V(G), E(G)) is an assignment c: E(G) → {1, 2, …, k} such that no two adjacent edges receive the same color. A neighbor sum distinguishing k-edge coloring of G is a proper k-edge coloring of G such that  for each edge uv ∈ E(G). The neighbor sum distinguishing index of a graph G is the least integer k such that G has such a coloring, denoted by χ’_Σ(G). Let be the maximum average degree of G. In this paper, we prove χ’_Σ(G) ≤ max{9, Δ(G) +1} for any normal graph G with . Our approach is based on the discharging method and Combinatorial Nullstellensatz.

Keywords

Proper Edge Coloring, Neighbor Sum Distinguishing Edge Coloring, Maximum Average Degree, Combinatorial Nullstellensatz

1. Introduction

All graphs mentioned in this paper are undirected, finite and simple. For a graph G, we denote its vertex set, edge set, maximum degree, minimum degree by $V\left(G\right)$, $E\left(G\right)$, $\Delta \left(G\right)$, $\delta \left(G\right)$, respectively. Let $N_G\left(v\right)$ be the set of neighbors of the vertex v in G, and $d_G\left(v\right)=\left|N_G\left(v\right)\right|$ be the degree of v in G. The

average degree of a graph G is defined as $\frac{2\left|E\left(G\right)\right|}{\left|V\left(G\right)\right|}$. The maximum average degree $mad\left(G\right)$ of G is the maximum of the average degrees of its subgraphs.

A proper k-edge coloring of a graph $G=\left(V\left(G\right)\mathrm{,}E\left(G\right)\right)$ is an assignment $c\mathrm{<mo>\; :\; </mo>}E\left(G\right)\to \left\{\mathrm{1,2,}\cdots \mathrm{,}k\right\}$ such that $c\left(e_1\right)\ne c\left(e_2\right)$ for any two adjacent edges $e_1$ and $e_2$. Let c be a proper k-edge coloring of G. We use $f\left(v\right)$ to denote the sum of colors of the edges incident to v. If $f\left(u\right)\ne f\left(v\right)$ for each edge $uv\in E\left(G\right)$, then c is called as a neighbor sum distinguishing k-edge coloring or an nsd-k-coloring of G for short. The neighbor sum distinguishing index of a graph G is the least integer k such that G has an nsd-k-coloring, denoted by ${{\chi }^{\prime }}_{\Sigma }\left(G\right)$. By $S\left(v\right)$, we denote the set of colors taken on the edges incident to v, i.e. $S\left(v\right)=\left\{c\left(uv\right)\mathrm{<mo>\; |\; </mo>}uv\in E\left(G\right)\right\}$. The proper k-edge coloring c is a neighbor set distinguishing k-edge coloring, if $S\left(u\right)\ne S\left(v\right)$ for each edge $uv\in E\left(G\right)$. Let ${{\chi }^{\prime }}_a\left(G\right)$ be the smallest value k such that G has a neighbor set distinguishing k-edge coloring. It is easy to observe that G has a neighbor sum(or set) distinguishing edge coloring if and only if G does not contain isolated edges. A graph with no isolated edges is called as a normal graph. Then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\ge {{\chi }^{\prime }}_a\left(G\right)$ for any normal graph by definition.

In 2002, Zhang et al. [1] introduced the concept of the neighbor set distinguishing edge coloring and posed the following conjecture.

Conjecture 1.1 ( [1] ) If G is a connected normal graph with at least 6 vertices, then ${{\chi }^{\prime }}_a\left(G\right)\le \Delta \left(G\right)+2$ .

Hatami [2] proved ${{\chi }^{\prime }}_a\left(G\right)\le \Delta \left(G\right)+300$ by probabilistic method for normal graph G with $\Delta \left(G\right)>{10}^{20}$. Akbari et al. [3] showed that ${{\chi }^{\prime }}_a\left(G\right)\le 3\Delta \left(G\right)$ for any normal graph. Wang et al. [4] improved this bound to that ${{\chi }^{\prime }}_a\left(G\right)\le 2.5\Delta \left(G\right)$ for any normal graph.

The neighbor sum distinguishing edge coloring was introduced by Flandrin et al. [5]. They determined the neighbor sum distinguishing index of graph classes including paths, trees, cycles, complete graphs and complete bipartite graphs, and posed the following conjecture.

Conjecture 1.2. ( [5] ) If G is a connected normal graph with at least 3 vertices and $G\ne C_5$ , then $\Delta \left(G\right)\le {{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+2$ .

Flandrin et al. [5] proved that ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \lceil \frac{7\Delta \left(G\right)-4}{2}\rceil$ for each connected normal graph G with maximum degree $\Delta \left(G\right)\ge 2$. Wang and Yan [6] improved this bound to $\lceil \frac{10\Delta \left(G\right)+2}{3}\rceil$. Bonamy and Przybylo [7] showed that ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+1$ for planar graph with $\Delta \left(G\right)\ge 28$. Dong et al. [8] studied the connections between neighbor sum distinguishing index and maximum average degree, and proved that if G is a normal graph with $mad\left(G\right)<\frac{5}{2}$ and $\Delta \left(G\right)\ge 5$, then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+1$. Later, Gao et al. [9] showed that if G is a normal graph with $mad\left(G\right)<\frac{8}{3}$ and $\Delta \left(G\right)\ge 5$, then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+1$. Hocquard and Przybylo [10] proved that ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+1$ for any normal graph G with $mad\left(G\right)<3$ and $\Delta \left(G\right)\ge 6$. Wang et al. [11] proved that if G is a normal graph with $mad\left(G\right)<\frac{37}{12}$ and $\Delta \left(G\right)\ge 7$, then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+2$. Recently, Wang et al. [12] proved that if G is a normal graph with $mad\left(G\right)<\frac{10}{3}$ and $\Delta \left(G\right)\ge 8$, then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+2$.

In this paper, we improve the result given by Wang et al. [11] and obtain the following result:

Theorem 1.1. Let G be a normal graph. If $mad\left(G\right)<\frac{37}{12}$ , then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \max \left\{9,\Delta \left(G\right)+1\right\}$ .

Corollary 1.2. Let G be a normal graph. If $mad\left(G\right)<\frac{37}{12}$ and $\Delta \left(G\right)\ge 8$ , then ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le \Delta \left(G\right)+1$ .

2. Preliminaries

To prove our main result, we need to introduce some notations. A vertex v is called a k-vertex (a $k^{+}$ -vertex, or a $k^{-}$ -vertex, respectively) if $d\left(v\right)=k$ ( $d\left(v\right)\ge k$, or $d\left(v\right)\le k$, respectively). A vertex v is called a leaf if $d\left(v\right)=1$.

At first, we introduce several lemmas.

Lemma 2.1. ( [11] ) Suppose that k and n are positive integers with $k\le n$ , $S_i$ is a set of integers with $\left|S_i\right|=l_i\ge n$ , $i=1,2,\cdots ,k$ . Let $T_k=\left\{{\displaystyle {\sum }_{i=1}^k}{x}_i|x_i\in S_i,x_i\ne x_j\left(i\ne j\right)\right\}$, then $\left|T_k\right|\ge {\displaystyle {\sum }_{i=1}^k}{l}_i-k^2+1$ .

Lemma 2.2. ( [13] ) Let F be an arbitrary field, and let $P=P\left(x_1,\cdots ,x_n\right)$ be a polynomial in $F\left[x_1,\cdots ,x_n\right]$ . Suppose the degree $deg\left(P\right)$ of P equals ${\displaystyle {\sum }_{i=1}^n}{k}_i$ , where each $k_i$ is a non-negative integer, and suppose the coefficient of $x_1^{k_1}\cdots x_n^{k_n}$ in P is non-zero. Then if $S_1\mathrm{,}\cdots \mathrm{,}{S}_n$ are subsets of F with $\left|S_i\right|>k_i$ , there are $s_1\in S_1\mathrm{,}\cdots \mathrm{,}{s}_n\in S_n$ so that $P\left(s_1\mathrm{,}\cdots \mathrm{,}{s}_n\right)\ne 0$ .

Lemma 2.3. ( [14] ) Let

$P\left(x_1,x_2,\cdots ,x_n\right)={\displaystyle \underset{1\le i<j\le n}{\prod }}\left(x_i-x_j\right){\left({\displaystyle \underset{k=1}{\overset{n}{\sum }}}{x}_k\right)}^2$

be a polynomial in n variables,where $n\ge 2$ .Let $C_P\left(x_1^{n_1}{x}_2^{n_2}\cdots x_n^{n_n}\right)$ denote the coefficient of $x_1^{n_1}{x}_2^{n_2}\cdots x_n^{n_n}$ in P,then

$C_P\left(x_1^n{x}_2^{n-1}{x}_3^{n-3}{x}_4^{n-4}\cdots x_{n-1}\right)=1.$

3. Proof of Theorem 1.1

3.1. Unavoidable Configuration

In this paper, we will prove Theorem 1.1 by contradiction. Let $K=\max \left\{9,\Delta \left(G\right)+1\right\}$. Let G be a counterexample of theorem 1.1 such that $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$ is the smallest. Obviously, G is connected. Let H be a normal subgraph of G. By the minimality of G, H has an nsd-K-coloring c using the color set $\left\{\mathrm{1,2,}\cdots \mathrm{,}K\right\}$.

Remark 1. Let $u\in V\left(G\right)$. Suppose that u is adjacent to a 2-vertex v with $N_G\left(v\right)=\left\{u\mathrm{,}w\right\}$ and $d_G\left(w\right)\le 4$. If $G^{\prime }=G-vw$ admits an nsd-K-coloring c such that $c\left(uv\right)\ne f\left(w\right)$, then there are at least $K-3-3-1-1\ge 1$ colors available for vw. Hence we can get an nsd-K-coloring of G. Hence, in the following discussion, we will omit the proof of recoloring or coloring of vw, and just show that $G^{\prime }=G-vw$ has an nsd-K-coloring c with $c\left(uv\right)\ne f\left(w\right)$.

Let H be the graph which is obtained by removing all the leaves of G. Let $d_k\left(v\right)$ ( $d_{k^{+}}\left(v\right)$, $d_{k^{-}}\left(v\right)$ ) be the number of neighbors of v with degree k (at most k, at least k) in H.

Claim 3.1. The graph H has the following properties:

(1) $\delta \left(H\right)\ge 2$.

(2) If $d_H\left(u\right)\le 4$, then $d_G\left(u\right)=d_H\left(u\right)$.

(3) If $uvw$ is a path in H such that $d_H\left(v\right)=2$, $2\le d_H\left(w\right)\le 4$, then $d_G\left(u\right)=d_H\left(u\right)$.

Proof: (1) This statement follows from [8].

(2) Assume to the contrary that $d_G\left(u\right)>d_H\left(u\right)=d$. Let $d_G\left(u\right)-d_H\left(u\right)=l\ge 1$. Then u in G is adjacent to d 2⁺-vertices $u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_d$ and l leaves $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_l$.

Suppose that $l=1$. Let $G^{\prime }=G-u{v}_1$. Then ${{\chi }^{\prime }}_{\Sigma }\left(G^{\prime }\right)\le K$ by the minimality of G. The colors in $\left\{c\left(u{u}_i\right)\mathrm{<mo>\; |\; </mo>1}\le i\le d\right\}\cup \left\{f\left(u_i\right)-f\left(u\right)\mathrm{<mo>\; |\; </mo>1}\le i\le d\right\}$ are forbidden for $u{v}_1$. So we have at least $K-2d\ge K-8\ge 1$ available colors for $u{v}_1$. Therefore, we can get an nsd-K-coloring of G, a contradiction.

Suppose that $2\le l\le \Delta \left(G\right)-d$. Let $G^{\prime }=G-\left\{u{v}_i|1\le i\le l\right\}$ and $S_i$ denote the feasible color set which $u{v}_i$ can use for each $1\le i\le l$. Then $\left|S_i\right|\ge K-d$ colors available for $u{v}_i$. By Lemma 2.1, $\left|T_l\right|\ge l\left(K-d\right)-l^2+1$. Let $f\left(l\right)=l\left(K-d\right)-l^2+1=l\left(K-d-l\right)+1$. Note that $K-d-l\ge \Delta \left(G\right)+1-d-l\ge 1$. If $l\ge 4$, then $f\left(l\right)\ge l+1>4$. If $2\le l\le 3$, then $K-d-l\ge 9-4-3\ge 2$ and $f\left(l\right)\ge 2\times 2+1>4$. Thus, we can show that $f\left(l\right)>4$. Hence we can get an nsd-K-coloring of G, a contradiction.

(3) According to Claim 3.1 (2), we have $d_G\left(v\right)=d_H\left(v\right)=2$ and $d_G\left(w\right)=d_H\left(w\right)$. Assume to the contrary that $d_G\left(u\right)>d_H\left(u\right)=d$, this means that there exist at least one leave $v_1$ adjacent to u in G. Let $G^{\prime }=G-vw$. Then $G^{\prime }$ has an nsd-K-coloring c by the minimality of G. If $c\left(uv\right)\ne f\left(w\right)$, we can get an nsd-K-coloring of G by Remark 1, a contradiction. If $c\left(uv\right)=f\left(w\right)$, then we exchange the colors of $u{v}_1$ and $uv$, and get an nsd-K-coloring of G by Remark 1, a contradiction. $\square$

A 2-vertex is called bad if it is adjacent to a 2-vertex; weak if it is adjacent to a 3-vertex or a 4-vertex; good if it is adjacent to two 5⁺-vertices; deficient if it is bad or weak. Let $d_{b2}\left(u\right)$ ( $d_{def}\left(v\right)$, $d_{g2}\left(u\right)$ ) be the number of bad 2-vertices (deficient vertices, good 2-vertices) adjacent to u in H.

Claim 3.2. Suppose that u is a weak 2-vertex in H. Let $N_H\left(u\right)=\left\{u_1\mathrm{,}{u}_2\right\}$, where $d_H\left(u_1\right)=3$ or 4.

(1) If $d_H\left(u_1\right)=3$, then $d_{5^{+}}\left(u_1\right)=2$.

(2) If $d_H\left(u_1\right)=4$, then $d_{4^{+}}\left(u_1\right)=3$.

Proof: (1) By Claim 3.1 (2), $d_G\left(u_1\right)=d_H\left(u_1\right)=3$ and $d_G\left(u\right)=d_H\left(u\right)=2$. Let $N_G\left(u_1\right)=\left\{u,x,y\right\}$. Assume to the contrary that $d_H\left(x\right)\le 4$. According to Claim 3.1 (2), $d_G\left(x\right)=d_H\left(x\right)\le 4$. Let $G^{\prime }=G-\left\{u{u}_1\mathrm{,}{u}_{1}x\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. It is easy to see that there are at least $K-3-3-1-1\ge 1$ available colors for $u_{1}x$. So we can extend the coloring to G by Remark 1, a contradiction.

(2) By Claim 3.1 (2), $d_G\left(u_1\right)=d_H\left(u_1\right)=4$ and $d_G\left(u\right)=d_H\left(u\right)=2$. Let $N_G\left(u_1\right)=\left\{u,x,y,z\right\}$. Assume to the contrary that $d_H\left(x\right)\le 3$. By Claim 3.1 (2), $d_G\left(x\right)=d_H\left(x\right)\le 3$. Let $G^{\prime }=G-\left\{u{u}_1\mathrm{,}{u}_{1}x\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. There are at least $K-2-2-2-1\ge 2$ available colors for $u_{1}x$. So we can obtain an nsd-K-coloring of G by Remark 1, a contradiction. $\square$

If $uxy$ is a path of H such that $d_H\left(y\right)=2$ and $d_H\left(x\right)=3$, then u is called the source vertex of y, y is called sink vertex of u. We use $s\left(u\right)$ to denote the number of sink vertices of u. By Claim 3.2 (1), we know that $s\left(u\right)\le d_3\left(u\right)$.

Claim 3.3 Let $u\in V\left(H\right)$ with $d_H\left(u\right)=d$. Let $u_1\mathrm{,}\cdots \mathrm{,}{u}_d$ be the neighbors of u in H.

(1) If $d=2$, then $d_{4^{-}}\left(u\right)\le 1$.

(2) If $d=3$, then $d_{3^{-}}\left(u\right)\le 1$.

(3) If $d\ge 5$, then $d_{b2}\left(u\right)\le 1$.

(4) If $d=5$, then $d_2\left(u\right)\le 2$.

(4.1) If $d_{def}\left(u\right)=1$, then $s\left(u\right)=0$.

(4.2) If $d_2\left(u\right)=2$, then $d_{def}\left(u\right)\le 1$.

(4.3) If $d_2\left(u\right)=2$ and $d_{def}\left(u\right)=1$, then $d_3\left(u\right)=0$.

(5) If $d=6$, then $d_{def}\left(u\right)\le 1$.

(5.1) If $d_{def}\left(u\right)=0$ and $d_{g2}\left(u\right)\ge 5$, then $d_{3^{-}}\left(u\right)=5$.

(5.2) If $d_{def}\left(u\right)=1$, then $d_{g2}\left(u\right)\le 1$.

Proof: (1) Assume to the contrary that u is adjacent to two 4^--vertices $u_1$ and $u_2$. By Claim 3.1 (2), $d_G\left(u\right)=d_H\left(u\right)=2$ and $d_G\left(u_i\right)=d_H\left(u_i\right)$ for $i=1,2$. Suppose that $u_1{u}_2\notin E\left(G\right)$ (If $u_1{u}_2\in E\left(G\right)$, we can prove it similarly). Let $G^{\prime }=G-u$. Then $G^{\prime }$ has an nsd-K-coloring c by the minimality of G. It is easy to show that the colors in $\left\{c\left(u_{1}w\right)\mathrm{<mo>\; |\; </mo>}w\in N_{G^{\prime }}\left(u_1\right)\right\}\cup \left\{f\left(w\right)-f\left(u_1\right)\mathrm{<mo>\; |\; </mo>}w\in N_{G^{\prime }}\left(u_1\right)\right\}\cup \left\{f\left(u_2\right)\right\}$ are forbidden for $u{u}_1$. So we have at least $K-3-3-1\ge 2$ available colors for $u{v}_1$. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.

(2) Assume to the contrary that u is adjacent to two 3^--vertices $u_1$ and $u_2$. By Claim 3.1 (2), $d_G\left(u\right)=d_H\left(u\right)=3$ and $d_G\left(u_i\right)=d_H\left(u_i\right)$ for $i=1,2$. Let $G^{\prime }=G-\left\{u{u}_1\mathrm{,}u{u}_2\right\}$. Then $G^{\prime }$ has an nsd-K-coloring c by the minimality of G. The colors in $\left\{c\left(u_{1}w\right)\mathrm{,}f\left(w\right)-f\left(u_1\right)\mathrm{<mo>\; |\; </mo>}w\in N_{G^{\prime }}\left(u_1\right)\right\}\cup \left\{c\left(u{u}_3\right)\mathrm{,}f\left(u_2\right)-c\left(u{u}_3\right)\right\}$ are forbidden for $u{u}_1$. So we have at least $K-2-2-1-1\ge 3$ available colors for $u{u}_1$. Next, there are at least $K-2-2-2-2\ge 1$ colors available for $u{u}_2$. Hence we have ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le K$, a contradiction.

(3) Assume to the contrary that u is adjacent to two bad 2-vertices $u_1$ and $u_2$. By Claim 3.1 (2), we have $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for $i=1,2$.

Case 1: $u_1{u}_2\in E\left(G\right)$.

Let $G^{\prime }=G-u_1{u}_2$. The colors in $\left\{f\left(u\right)-c\left(u{u}_1\right)\mathrm{,}f\left(u\right)-c\left(u{u}_2\right)\mathrm{,}c\left(u{u}_1\right)\mathrm{,}c\left(u{u}_2\right)\right\}$ are forbidden for $u_1{u}_2$. So there are at least $K-4\ge 5$ available colors for $u_1{u}_2$. Hence, we can extend this coloring to G, a contradiction.

Case 2: $u_1{u}_2\notin E\left(G\right)$.

Let $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for $i=1,2$. By Claim 3.1 (2), $d_G\left(w_i\right)=d_H\left(w_i\right)=2$ for $i=1,2$. By Claim 3.2 (1), $w_1\ne w_2$ and $w_1{w}_2\notin E\left(G\right)$. Let $N_G\left(w_i\right)=\left\{u_i\mathrm{,}{v}_i\right\}$ for $i=1,2$.

Case 2.1: $v_1=v_2=v$.

Let $G^{\prime }=G-\left\{u_1{w}_1,u_2{w}_2\right\}$. Then $G^{\prime }$ has an nsd-K-coloring c by the minimality of G. Note that $c\left(u{u}_1\right)\ne c\left(u{u}_2\right)$ and $c\left(v{w}_1\right)\ne c\left(v{w}_2\right)$. If $c\left(u{u}_1\right)=c\left(v{w}_1\right)$ (similarly for $c\left(u{u}_2\right)=c\left(v{w}_2\right)$ ), then we switch the colors of $u{u}_1$ and $u{u}_2$. It is worth noting that $f\left(u_1\right)\ne f\left(w_1\right)$ and $f\left(u_2\right)\ne f\left(w_2\right)$ for this new nsd-K-coloring $c^{\prime }$ of $G^{\prime }$. The colors in $\left\{c^{\prime }\left(u{u}_1\right)\mathrm{,}f\left(u\right)-c^{\prime }\left(u{u}_1\right)\mathrm{,}{c}^{\prime }\left(v{w}_1\right)\mathrm{,}f\left(v\right)-c^{\prime }\left(v{w}_1\right)\right\}$ are forbidden for $u_1{w}_1$. So we have at least $K-1-1-1-1\ge 5$ available colors for $u_1{w}_1$. Similarly, there are at least 5 colors available for $u_2{w}_2$. Hence we have ${{\chi }^{\prime }}_{\Sigma }\left(G\right)\le K$, a contradiction. If $c\left(u{u}_1\right)\ne c\left(v{w}_1\right)$ and $c\left(u{u}_2\right)\ne c\left(v{w}_2\right)$, then $f\left(u_i\right)\ne f\left(w_i\right)$ ( $i=1,2$ ). Now we can extend this coloring to G with the similar discussion as above, a contradiction.

Case 2.2: $v_1\ne v_2$.

Let $G^{\prime }=G-\left\{u_1{w}_1\mathrm{,}{u}_2{w}_2\right\}+\left\{w_1{w}_2\right\}$. Now we will show that $mad\left(G^{\prime }\right)<\frac{37}{12}$. In fact, let $H^{\prime }$ be the subgraph of $G^{\prime }$. If $w_1{w}_2\notin E\left(H^{\prime }\right)$, then $H^{\prime }\subseteq G$ and $mad\left(H^{\prime }\right)<\frac{37}{12}$. So suppose that $w_1{w}_2\in E\left(H^{\prime }\right)$. If at most one of $w_1{v}_1$ and $w_2{v}_2$ belongs to $E\left(H^{\prime }\right)$, say $w_1{v}_1\in E\left(H^{\prime }\right)$ if it exists, then $H=H^{\prime }-w_2$, is the subgraph of G. Note that $\frac{2\left|E\left(H\right)\right|}{\left|V\left(H\right)\right|}<\frac{37}{12}$. Therefore, $\frac{2\left|E\left(H^{\prime }\right)\right|}{\left|V\left(H^{\prime }\right)\right|}=\frac{2\left(\left|E\left(H\right)\right|+1\right)}{\left|V\left(H\right)\right|+1}=\frac{2\left|E\left(H\right)\right|+2}{\left|V\left(H\right)\right|+1}<\frac{\frac{37}{12}\left|V\left(H\right)\right|+2}{\left|V\left(H\right)\right|+1}<\frac{37}{12}$. If $w_1{v}_1\in E\left(H^{\prime }\right)$ and $w_2{v}_2\in E\left(H^{\prime }\right)$, then $H=H^{\prime }-\left\{w_1,w_2\right\}$ is the subgraph of G. Note that $\frac{2\left|E\left(H\right)\right|}{\left|V\left(H\right)\right|}<\frac{37}{12}$. Therefore, $\frac{2\left|E\left(H^{\prime }\right)\right|}{\left|V\left(H^{\prime }\right)\right|}=\frac{2\left(\left|E\left(H\right)\right|+3\right)}{\left|V\left(H\right)\right|+2}=\frac{2\left|E\left(H\right)\right|+6}{\left|V\left(H\right)\right|+2}<\frac{\frac{37}{12}\left|V\left(H\right)\right|+6}{\left|V\left(H\right)\right|+2}<\frac{37}{12}$. Thus, we obtain that $G^{\prime }$ is a graph with $mad\left(G^{\prime }\right)<\frac{37}{12}$ and $\left|E\left(G^{\prime }\right)\right|+\left|V\left(G^{\prime }\right)\right|<\left|E\left(G\right)\right|+\left|V\left(G\right)\right|$. Then $G^{\prime }$ has an nsd-K-coloring c by the minimality of G. Note that $c\left(w_1{v}_1\right)\ne c\left(w_2{v}_2\right)$ by $f\left(w_1\right)\ne f\left(w_2\right)$. Then we can achieve an nsd-K-coloring of G with the similar discussion as Case 2.1.

(4) Assume to the contrary that u in H is adjacent to three 2-vertices $u_1,u_2$ and $u_3$. By Claim 3.1 (2), it holds that $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for $i\in \left\{\mathrm{1,2,3}\right\}$. Let $N_G\left(u_i\right)=\left\{u,w_i\right\}$ for each $i\in \left\{\mathrm{1,2,3}\right\}$. Assume that u in G is adjacent to l leaves $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_l$ with $l\ge 0$.

Case 1: $l=0$.

Then $d_G\left(u\right)=d_H\left(u\right)=5$. Let $G^{\prime }=G-\left\{u{u}_i|i=1,2,3\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. It is easy to see that there are at least $K-2-1-1\ge 5$ colors available for $u{u}_i$ ( $i\in \left\{\mathrm{1,2,3}\right\}$ ). By Lemma 2.1, $5\times 3-3^2+1=7>5$. So we can color $u{u}_1$, $u{u}_2$ and $u{u}_3$ properly such that $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le 5$, a contradiction.

Case 2: $l=1$.

Let $G^{\prime }=G-\left\{u{v}_1,u{u}_1,u{u}_2,u{u}_3\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. It is evident that there are at least $K-2-1-1\ge 5$ colors available for $u{u}_i$ ( $i\in \left\{\mathrm{1,2,3}\right\}$ ) and at least $K-2\ge 7$ colors available for $u{v}_1$. By Lemma 2.1, $7+5\times 3-4^2+1=7>5$. So we can color $u{v}_1$, $u{u}_1$, $u{u}_2$ and $u{u}_3$ properly and obtain an nsd-K-coloring of G, which is a contradiction.

Case 3: $l\ge 2$.

Let $G^{\prime }=G-\left(\left\{u{v}_i\mathrm{<mo>\; |\; </mo>}i=\mathrm{1,2,}\cdots \mathrm{,}m\right\}\cup \left\{u{u}_1\right\}\right)$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We use colors $x_1\mathrm{,}\cdots \mathrm{,}{x}_m\mathrm{,}{x}_{m+1}$ to color $u{v}_1\mathrm{,}\cdots \mathrm{,}u{v}_m\mathrm{,}u{u}_1$. Let $S_i$ and $S_{m+1}$ devote the available color set for $u{v}_i$ ( $1\le i\le m$ ) and $u{u}_1$, respectively. Now we consider the following polynomial:

$\begin{array}{c}P\left(x_1,\cdots ,x_{m+1}\right)={\displaystyle \underset{1\le i<j\le m+1}{\prod }}\left(x_i-x_j\right){\displaystyle \underset{n=2}{\overset{5}{\prod }}}\left({\displaystyle \underset{i=1}{\overset{m+1}{\sum }}}{x}_i+{\displaystyle \underset{t=s+1}{\overset{l}{\sum }}}c\left(u{v}_t\right)+{\displaystyle \underset{k=2}{\overset{5}{\sum }}}c\left(u{u}_k\right)-f\left(u_n\right)\right)\\ \cdot \left({\displaystyle \underset{i=1}{\overset{m+1}{\sum }}}{x}_i+{\displaystyle \underset{t=m+1}{\overset{l}{\sum }}}c\left(u{v}_t\right)+{\displaystyle \underset{k=2}{\overset{5}{\sum }}}c\left(u{u}_k\right)-x_{m+1}-f\left(u_1\right)\right).\end{array}$

Let

$Q\left(x_1,\cdots ,x_{m+1}\right)={\displaystyle \underset{1\le i<j\le m+1}{\prod }}\left(x_i-x_j\right){\left({\displaystyle \underset{i=1}{\overset{m+1}{\sum }}}{x}_i\right)}^4\left({\displaystyle \underset{i=1}{\overset{m}{\sum }}}{x}_i\right).$

Suppose that $l=2$. Let $m=2$. Notice that $\left|S_1\right|=\left|S_2\right|\ge K-\left(7-3\right)\ge 5$ and $\left|S_3\right|\ge K-\left(7-3\right)-1-1\ge 3$. By computations, we obtain that $C_P\left(x_1^4{x}_2^3{x}_3\right)=C_Q\left(x_1^4{x}_2^3{x}_3\right)=3\ne 0$. According to Lemma 2.2, we can choose $x_i\in S_i$ ( $1\le i\le m+1$ ) such that $P\left(x_1\mathrm{,}\cdots \mathrm{,}{x}_{m+1}\right)\ne 0$. That is, we can get an nsd-K-coloring of G, a contradiction.

Suppose that $l\ge 3$. Let $m=3$. It is evident that for each $1\le i\le m$, we have $\left|S_i\right|\ge K-\left(d_G\left(u\right)-4\right)\ge 5$ and $\left|S_{m+1}\right|\ge K-\left(d_G\left(u\right)-4\right)-1-1\ge 3$. By computations, we obtain that $C_P\left(x_1^4{x}_2^3{x}_3^2{x}_4^2\right)=C_Q\left(x_1^4{x}_2^3{x}_3^2{x}_4^2\right)=-1\ne 0$. According to Lemma 2.2, we can choose $x_i\in S_i$ ( $1\le i\le m+1$ ) such that $P\left(x_1\mathrm{,}\cdots \mathrm{,}{x}_{m+1}\right)\ne 0$. That is, we can get an nsd-K-coloring of G, a contradiction.

(4.1) Assume to the contrary that u in H is adjacent to one deficient vertex $u_1$ and has one sink vertex x. Let $u_2\in N_G\left(x\right)\cap N_G\left(u\right)$. Then by the definition of sink vertex, we have $d_H\left(u_2\right)=3$, $d_H\left(x\right)=2$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=5$, $d_G\left(u_1\right)=d_H\left(u_1\right)=2$, $d_G\left(u_2\right)=d_H\left(u_2\right)=3$ and $d_G\left(x\right)=d_H\left(x\right)=2$. Suppose that $N_G\left(u_1\right)=\left\{u,w_1\right\}$. Let $G^{\prime }=G-u{u}_1$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the colors on edges $u_1{w}_1$ and $u_{2}x$. There are at least $K-4-1\ge 4$ available colors for $u{u}_1$. Thus, we can color properly the edge $u{u}_1$ such that $f\left(u\right)\ne f\left(u_i\right)$ for $i\in \left\{\mathrm{3,4,5}\right\}$. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.

(4.2) Assume to the contrary that u in H is adjacent to two deficient vertices $u_1$ and $u_2$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=5$, $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ and $d_G\left(w_i\right)=d_H\left(w_i\right)\le 4$ ( $i=1,2$ ). Suppose that $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for each $i=1,2$. Let $G^{\prime }=G-\left\{u{u}_1\mathrm{,}u{u}_2\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the colors on edges $u_i{w}_i$ for $i=1,2$. There are at least $K-3-1\ge 5$ available colors for $u{u}_1$. So we can color $u{u}_1$. Next, we have at least $K-4-1\ge 4$ colors available for $u{u}_2$. Thus, we can color properly the edge $u{u}_2$ such that $f\left(u\right)\ne f\left(u_i\right)$ for $i\in \left\{\mathrm{3,4,5}\right\}$. Then we can get an nsd-K-coloring of G by Remark 1, a contradiction.

(4.3) Assume that u in H is adjacent to one deficient vertex $u_1$, one good 2-vertex $u_2$ and one 3-vertex $u_3$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=5$, $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ ( $i=1,2$ ) and $d_G\left(w_1\right)=d_H\left(w_1\right)\le 4$. Suppose that $N_G\left(u_i\right)=\left\{u,w_i\right\}$ for each $i=1,2$. Let $G^{\prime }=G-\left\{u{u}_i|i=1,2,3\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. Firstly, we erase the colors on edge $u_1{w}_1$. Then there are at least $K-2-1\ge 6$ available colors for $u{u}_1$ and at least $K-2-1-1\ge 5$ available colors for $u{u}_2$, and at least $K-2-2-2\ge 3$ colors available for $u{u}_3$. By Lemma 2.1, $6+5+3-3^2+1=6>5$. So we can color $u{u}_1$, $u{u}_2$ and $u{u}_3$ properly and obtain an nsd-K-coloring of G by Remark 1, which is a contradiction.

(5) Assume that u of H is adjacent to two deficient vertices $u_1$ and $u_2$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=6$, $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ and $d_G\left(w_i\right)=d_H\left(w_i\right)\le 4$ for $i=1,2$. Suppose that $N_G\left(u_i\right)=\left\{u,w_i\right\}$ for $i=1,2$. Let $G^{\prime }=G-\left\{u{u}_1,u{u}_2\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the colors on edges $u_i{w}_i$ ( $i=1,2$ ). Then there are at least $K-4-1\ge 4$ available colors for $u{u}_i$. By Lemma 2.1, $4\times 2-2^2+1=5>4$. So we can color $u{u}_1$ and $u{u}_2$ properly such that $f\left(u\right)\ne f\left(v\right)$ for $v\in N_G\left(u\right)-\left\{u_1\mathrm{,}{u}_2\right\}$. Hence, we obtain an nsd-K-coloring of G by Remark 1, a contradiction.

(5.1) Assume to the contrary that u in H is adjacent to five good 2-vertices $u_1$, $u_2$, $u_3$, $u_4$, $u_5$ and one $3^{-}$ -vertex $u_6$. By Claim 3.1 (2), it holds that $d_G\left(u_i\right)=d_H\left(u_i\right)$ for each $1\le i\le 6$. Assume that u in G is adjacent to l leaves $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_l$ with $l\ge 0$.

Suppose that $l=0$. Then $d_G\left(u\right)=d_H\left(u\right)=6$. Let $G^{\prime }=G-\left\{u{u}_1\mathrm{,}u{u}_2\right\}$. Then

$G^{\prime }$ has an nsd-K-coloring by the minimality of G. When $6=d_G\left(u\right)\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$, i.e. $\Delta \left(G\right)\ge 11$, we know that there are at least $K-4-1-1=\Delta \left(G\right)-5\ge 6$ colors available for $u{u}_i$ ( $i=1,2$ ). By Lemma 2.1, $6\times 2-2^2+1=9>6$. So we can color $u{u}_1$ and $u{u}_2$ properly such that $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le 6$, a contradiction. When $6=d_G\left(u\right)\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$, then $1+2+\cdots +5>\Delta \left(G\right)+1$. So we have $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le 5$. There are at least $K-4-1-1\ge 3$ available colors for $u{u}_i$ ( $i=1,2$ ). By Lemma 2.1, $3\times 2-2^2+1=3>1$. Thus, we can color properly the edges $u{u}_1$ and $u{u}_2$ such that $f\left(u\right)\ne f\left(u_6\right)$, a contradiction.

Suppose that $l\ge 1$. Let $G^{\prime }=G-u{v}_1$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. When $6+l=d_G\left(u\right)\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$, i.e. $\Delta \left(G\right)\ge 2l+11$, it is evident that there are at least $K-\left(6+l-1\right)-6\ge l+1$ colors available for $u{v}_1$. So we get an nsd-K-coloring of G, a contradiction. When $6+l=d_G\left(u\right)\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$, then $1+2+\cdots +\left(5+l\right)>\Delta \left(G\right)+1$. So we have $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le 5$. There are at least $K-\left(d_G\left(u\right)-1\right)-1\ge 1$ available colors for $u{v}_1$. Then we get an nsd-K-coloring of G, a contradiction.

(5.2) Assume that u of H is adjacent to a deficient vertex $u_1$ and two good 2-vertices $u_2$ and $u_3$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=6$, $d_G\left(w_1\right)=d_H\left(w_1\right)\le 4$ and $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for each $1\le i\le 3$. Let $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for $1\le i\le 3$. Let $G^{\prime }=G-\left\{u{u}_i|i=1,2,3\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the colors on edges $u_1{w}_1$. For each $1\le i\le 3$, we use $x_i$ to color $u{u}_i$. Let $S_i$ be the available color set for $u{u}_i$. Then $\left|S_1\right|\ge K-3-1\ge 5$ and $\left|S_2\right|=\left|S_3\right|\ge K-3-1-1\ge 4$. Now we consider the following polynomial:

$\begin{array}{c}P\left(x_1,x_2,x_3\right)={\displaystyle \underset{1\le i<j\le 3}{\prod }}\left(x_i-x_j\right){\displaystyle \underset{n=1}{\overset{3}{\prod }}}\left({\displaystyle \underset{i=1}{\overset{3}{\sum }}}{x}_i+{\displaystyle \underset{k=4}{\overset{6}{\sum }}}c\left(u{u}_k\right)-x_n-f\left(u_n\right)\right)\\ \cdot {\displaystyle \underset{n=4}{\overset{6}{\prod }}}\left({\displaystyle \underset{i=1}{\overset{3}{\sum }}}{x}_i+{\displaystyle \underset{k=4}{\overset{6}{\sum }}}c\left(u{u}_k\right)-f\left(u_n\right)\right).\end{array}$

Let

$Q\left(x_1,x_2,x_3\right)={\displaystyle \underset{1\le i<j\le 3}{\prod }}\left(x_i-x_j\right){\displaystyle \underset{n=1}{\overset{3}{\prod }}}\left({\displaystyle \underset{i=1}{\overset{3}{\sum }}}{x}_i-x_n\right){\left({\displaystyle \underset{i=1}{\overset{3}{\sum }}}{x}_i\right)}^3.$

By matlab, we obtain that $C_P\left(x_1^4{x}_2^3{x}_3^2\right)=2\ne 0$. According to Lemma 2.2, we can choose $x_i\in S_i$ ( $1\le i\le 3$ ) such that $P\left(x_1\mathrm{,}{x}_2\mathrm{,}{x}_3\right)\ne 0$. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction. $\square$

Remark 2. Note that if $d_G\left(u\right)\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$, then $1+2+\cdots +\left(d_G\left(u\right)-1\right)\ge 1+2+\cdots +\lceil \frac{\Delta \left(G\right)}{2}\rceil >\Delta \left(G\right)+1$. So $f\left(u\right)\ne f\left(u_i\right)$ when $d_G\left(u_i\right)=2$ for any proper edge coloring of G.

Claim 3.4. Let $u\in V\left(H\right)$ with $d_H\left(u\right)=d$. Suppose that $7\le d\le \Delta \left(G\right)-1$.

(1) $d_2\left(u\right)\le d-1$.

(2) If $d\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$, then $d_{def}\left(u\right)=0$.

(3) If $d\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$, then $d_{def}\left(u\right)\le \lceil \frac{d}{2}\rceil -1$.

(3.1) If $d_{def}\left(u\right)=1$, then $d_2\left(u\right)\le d-3$.

(3.2) If $d_{def}\left(u\right)=\lceil \frac{d}{2}\rceil -1$, then $d_{g2}\left(u\right)\le 1$.

Proof: (1) Assume to the contrary that u in H is adjacent to d 2-vertices $u_1,\cdots ,u_d$. By Claim 3.1 (2), we have $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for each $1\le i\le d$. Assume that u in G is adjacent to l leaves $v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_l$.

Suppose that $l=0$. Then $d_G\left(u\right)=d_H\left(u\right)=d$. Let $G^{\prime }=G-u$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. If $7\le d\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$. Then $\Delta \left(G\right)\ge 2d-1$. There are at least $K-1-1\ge \Delta \left(G\right)-1$ colors available for $u{u}_i$ ( $1\le i\le d$ ). By Lemma 2.1, $\left(\Delta \left(G\right)-1\right)d-d^2+1\ge \left(d-2\right)d+1>d$. So we can color $u{u}_i$ properly such that $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le d$. So we get an nsd-K-coloring of G, a contradiction. So suppose that $d\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$. By Remark 2, $f\left(u\right)\ne f\left(u_i\right)$ ( $1\le i\le d$ ) for any proper edge coloring of G. Note that there are at least $K-1-1=\Delta \left(G\right)-1\ge d$ available colors for $u{u}_i$ ( $1\le i\le d$ ). Hence, we get an nsd-K-coloring of G, a contradiction.

Suppose that $l\ge 1$. Let $G^{\prime }=G-u{v}_1$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. If $d+l\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$, i.e. $\Delta \left(G\right)\ge 2d+2l-1$, then there are at least $K-\left(d+l-1\right)-d\ge l+1$ colors available for $u{v}_1$. So we get an nsd-K-coloring of G, a contradiction. If $d+l\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$, then $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le d$ for any proper coloring of G by Remark 2. Note that there are at least $K-\left(d_G\left(u\right)-1\right)\ge 2$ available colors for $u{v}_1$. Hence, we get an nsd-K-coloring of G, a contradiction.

(2) Assume that u of H is adjacent to a deficient vertex $u_1$. Let $N_G\left(u_1\right)=\left\{u,w_1\right\}$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=d\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$, $d_G\left(u_1\right)=d_H\left(u_1\right)=2$ and $d_G\left(w_1\right)=d_H\left(w_1\right)\le 4$. Let $G^{\prime }=G-u_1$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. There are at least $K-2\left(d-1\right)-1\ge \Delta \left(G\right)-2\lceil \frac{\Delta \left(G\right)}{2}\rceil +2\ge 1$ available colors for $u{u}_1$. Hence, we can get an nsd-K-coloring of G by Remark 1, a contradiction.

(3) Assume to the contrary that u in H is adjacent to $\lceil \frac{d}{2}\rceil$ deficient vertices $u_1\mathrm{,}{u}_2\mathrm{,}\cdots \mathrm{,}{u}_{\lceil \frac{d}{2}\rceil }$. Let $N_G\left(u_i\right)=\left\{u,w_i\right\}$ for each $1\le i\le \lceil \frac{d}{2}\rceil$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=d$, $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ and $d_G\left(w_i\right)=d_H\left(w_i\right)\le 4$ for $1\le i\le \lceil \frac{d}{2}\rceil$. Let $G^{\prime }=G-\left\{u{u}_i|i=1,2,\cdots ,\lceil \frac{d}{2}\rceil \right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the colors on edges $u_i{w}_i$ for each $1\le i\le \lceil \frac{d}{2}\rceil$. There are at least $K-\left(d-\lceil \frac{d}{2}\rceil \right)-1\ge \Delta \left(G\right)-d+\lceil \frac{d}{2}\rceil \ge \lceil \frac{d}{2}\rceil +1$ available colors for $u{u}_i$ ( $1\le i\le \lceil \frac{d}{2}\rceil$ ). By Lemma 2.1, $\left(\lceil \frac{d}{2}\rceil +1\right)\times \lceil \frac{d}{2}\rceil -{\lceil \frac{d}{2}\rceil }^2+1=\lceil \frac{d}{2}\rceil +1>d-\lceil \frac{d}{2}\rceil$. So we can color $u{u}_i$ properly such that $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le d$. Hence, we get an nsd-K-coloring of G by Remark 1, a contradiction.

(3.1) Assume that u of H is adjacent to $\left(d-2\right)$ 2-vertices $u_1\mathrm{,}\cdots \mathrm{,}{u}_{d-2}$ such that $u_1$ is a deficient vertex. Let $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for $1\le i\le d-2$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=d$, $d_G\left(w_1\right)=d_H\left(w_1\right)\le 4$ and $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for each $1\le i\le d-2$. Let $G^{\prime }=G-\left\{u{u}_i|i=1,2,\cdots ,d-2\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. Firstly, we erase the colors on edge $u_1{w}_1$. For each $1\le i\le d-2$, we use $x_i$ to color $u{u}_i$. Let $S_i$ be the available color set for $u{u}_i$. Then $\left|S_1\right|\ge K-2-1=\Delta \left(G\right)-2\ge d-1$ and $\left|S_i\right|\ge K-2-1-1\ge d-2$ ( $2\le i\le d-2$ ). Now we consider the following polynomial:

$P\left(x_1,x_2,\cdots ,x_{d-2}\right)={\displaystyle \underset{1\le i<j\le d-2}{\prod }}\left(x_i-x_j\right){\displaystyle \underset{n=d-1}{\overset{d}{\prod }}}\left({\displaystyle \underset{i=1}{\overset{d-2}{\sum }}}{x}_i+{\displaystyle \underset{k=d-1}{\overset{d}{\sum }}}c\left(u{u}_k\right)-f\left(u_n\right)\right).$

Let

$Q\left(x_1,x_2,\cdots ,x_{d-2}\right)={\displaystyle \underset{1\le i<j\le d-2}{\prod }}\left(x_i-x_j\right){\left({\displaystyle \underset{i=1}{\overset{d-2}{\sum }}}{x}_i\right)}^2.$

By Lemma 2.3, we obtain that $C_Q\left(x_1^{d-2}{x}_2^{d-3}{x}_3^{d-5}{x}_4^{d-6}\cdots x_{d-3}\right)=1\ne 0$. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction.

(3.2) Assume to the contrary that, u in H is adjacent to ( $\lceil \frac{d}{2}\rceil +1$ ) 2-vertices $u_1\mathrm{,}\cdots \mathrm{,}{u}_{\lceil \frac{d}{2}\rceil +1}$ such that $u_1\mathrm{,}\cdots \mathrm{,}{u}_{\lceil \frac{d}{2}\rceil -1}$ are deficient vertices. Then $u_{\lceil \frac{d}{2}\rceil }$ and $u_{\lceil \frac{d}{2}\rceil +1}$ are good 2-vertices by Claim 3.4 (3). Let $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for each $1\le i\le \lceil \frac{d}{2}\rceil +1$. By Claim 3.1, it holds that $d_G\left(u\right)=d_H\left(u\right)=d$, $d_G\left(u_i\right)=d_H\left(u_i\right)=2$ for $1\le i\le \lceil \frac{d}{2}\rceil +1$. Consider that $G^{\prime }=G-\left\{u{u}_i|i=1,2,\cdots ,\lceil \frac{d}{2}\rceil +1\right\}$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality of G. We erase the color on edge $u_i{w}_i$ for each $1\le i\le \lceil \frac{d}{2}\rceil -1$. There are at least $K-\left(d-\lceil \frac{d}{2}\rceil -1\right)-1\ge \Delta \left(G\right)-d+\lceil \frac{d}{2}\rceil +1\ge \lceil \frac{d}{2}\rceil +2$ available colors for $u{u}_i$ ( $1\le i\le \lceil \frac{d}{2}\rceil -1$ ), at least $K-\left(d-\lceil \frac{d}{2}\rceil -1\right)-1-1\ge \lceil \frac{d}{2}\rceil +1$ available colors for $u{u}_i$ ( $i=\lceil \frac{d}{2}\rceil \mathrm{,}\lceil \frac{d}{2}\rceil +1$ ). By Lemma 2.1, $\left(\lceil \frac{d}{2}\rceil +2\right)\left(\lceil \frac{d}{2}\rceil -1\right)+2\left(\lceil \frac{d}{2}\rceil +1\right)-{\left(\lceil \frac{d}{2}\rceil +1\right)}^2+1=\lceil \frac{d}{2}\rceil >d-\lceil \frac{d}{2}\rceil -1$. So we can color $u{u}_i$ properly such that $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le d$. Thus, we get an nsd-K-coloring of G by Remark 1, a contradiction. $\square$

Claim 3.5. Let $u\in V\left(H\right)$ with $d_H\left(u\right)=\Delta \left(G\right)\ge 7$. If $d_{def}\left(u\right)=1$ and $d_2\left(u\right)=\Delta \left(G\right)-1$, then $d_{3^{-}}\left(u\right)=\Delta \left(G\right)-1$.

Proof: Assume that u of H is adjacent to $\Delta \left(G\right)$ 3⁻-vertices $u_1\mathrm{,}\cdots \mathrm{,}{u}_{\Delta \left(G\right)}$ such that $u_1$ is a deficient vertex and $u_2\mathrm{,}\cdots \mathrm{,}{u}_{\Delta \left(G\right)-1}$ are 2-vertices. By Claim 3.1, it holds that $d_G\left(u_i\right)=d_H\left(u_i\right)$. Suppose that $N_G\left(u_i\right)=\left\{u\mathrm{,}{w}_i\right\}$ for each $1\le i\le d-1$. Let $G^{\prime }=G-u{u}_1$. Then $G^{\prime }$ has an nsd-K-coloring by the minimality

of G. Since $1+2+\cdots +\left(\Delta \left(G\right)-1\right)=\frac{\Delta \left(G\right)\left(\Delta \left(G\right)-1\right)}{2}>2\Delta \left(G\right)+1$, then we can

get $f\left(u\right)\ne f\left(u_i\right)$ for each $1\le i\le \Delta \left(G\right)$. Firstly, we erase the color on edge $u_1{w}_1$. There are at least $K-\left(\Delta \left(G\right)-1\right)-1\ge 1$ available colors for $u{u}_1$. Thus, we obtain an nsd-K-coloring of G by Remark 1, a contradiction. $\square$

3.2. Discharging Process

In order to complete the proof of Theorem 1.1, we use the discharging method. For this aim we first define the original charge function $w\left(u\right)=d_H\left(u\right)-\frac{37}{12}$ for each $u\in V\left(H\right)$, then

${\displaystyle \underset{u\in V\left(H\right)}{\sum }}w\left(u\right)={\displaystyle \underset{u\in V\left(H\right)}{\sum }}\left(d_H\left(u\right)-\frac{37}{12}\right)\le \left|V\left(H\right)\right|\left(mad\left(G\right)-\frac{37}{12}\right)<0.$

We will design several discharging rules and reassign the charges according to the rules below. Let $w^{\ast }$ be the final charge. We will show that for each $u\in V\left(H\right)$, $w^{\ast }\left(u\right)\ge 0$. This leads to the following contradiction:

$0\le {\displaystyle \underset{u\in V\left(H\right)}{\sum }}{w}^{\ast }\left(u\right)={\displaystyle \underset{u\in V\left(H\right)}{\sum }}w\left(u\right)<0$

and it shows the nonexistence of G.

We define the discharging rules as follows:

(R1) Every 5⁺-vertex gives $\frac{13}{12}$ to each adjacent bad 2-vertex; $\frac{15}{24}$ to each adjacent weak 2-vertex; $\frac{13}{24}$ to each adjacent good 2-vertex.

(R2) Every source vertex gives $\frac{11}{48}$ to its sink vertex.

(R3) Every 4-vertex gives $\frac{11}{24}$ to each adjacent 2-vertex.

(R4) Every 4⁺-vertex gives $\frac{1}{24}$ to each adjacent 3-vertex.

Now we are going to show $w^{\ast }\left(v\right)\ge 0$ for each $u\in V\left(H\right)$. Let $u\in V\left(H\right)$ with $d_H\left(u\right)=d$. By Claim 3.1 (1), $d\ge 2$.

(1) $d=2$. According to Claim 3.3 (1), u is adjacent to at least one 5⁺-vertex. First, suppose that u is a bad 2-vertex. Then by (R1), $w^{\ast }\left(u\right)=2-\frac{37}{12}+\frac{13}{12}=0$. Next, suppose that u is a weak 2-vertex. If u is adjacent to a 3-vertex, then u has two source vertices. By (R1) and (R2), $w^{\ast }\left(u\right)=2-\frac{37}{12}+\frac{15}{24}+2\times \frac{11}{48}=0$. If u is adjacent to a 4-vertex, then by (R1) and (R3), $w^{\ast }\left(u\right)=2-\frac{37}{12}+\frac{15}{24}+\frac{11}{24}=0$. Finally, suppose that u is a good 2-vertex, by (R1), $w^{\ast }\left(u\right)=2-\frac{37}{12}+2\times \frac{13}{24}=0$.

(2) $d=3$. According to Claim 3.3 (2), u is adjacent to at least two 4⁺-vertex. Then by (R4), $w^{\ast }\left(u\right)=3-\frac{37}{12}+2\times \frac{1}{24}=0$.

(3) $d=4$. If u is adjacent to 2-vertex, then by Claim 3.2 (2), $d_{4^{+}}\left(u\right)=3$. By (R3), $w^{\ast }\left(u\right)=4-\frac{37}{12}-\frac{11}{24}=\frac{11}{24}$. If u is not adjacent to 2-vertex, then by (R4), $w^{\ast }\left(u\right)\ge 4-\frac{37}{12}-4\times \frac{1}{24}=\frac{3}{4}$.

(4) $d\ge 5$. It is trivial that $s\left(u\right)\le d_3\left(u\right)$. Hence we have:

$\begin{array}{c}{w}^{\ast }\left(u\right)\ge d-\frac{37}{12}-\frac{13}{12}{d}_{b2}\left(u\right)-\frac{15}{24}\left(d_{def}\left(u\right)-d_{b2}\left(u\right)\right)\\ -\frac{13}{24}{d}_{g2}\left(u\right)-\frac{11}{48}s\left(u\right)-\frac{1}{24}{d}_3\left(u\right)\\ \ge d-\frac{37}{12}-\frac{15}{24}{d}_{def}\left(u\right)-\frac{11}{24}{d}_{b2}\left(u\right)-\frac{13}{24}{d}_{g2}\left(u\right)-\frac{13}{48}{d}_3\left(u\right).\end{array}$ (1)

(4.1) $d=5$. According to Claim 3.3 (4), $d_2\left(u\right)\le 2$. By Claim 3.3 (3), $d_{b2}\left(u\right)\le 1$.

Suppose that $d_2\left(u\right)=2$. By Claim 3.3 (4.2), $d_{def}\left(u\right)\le 1$. Furthermore, if $d_{def}\left(u\right)=1$, then $d_3\left(u\right)=0$. Suppose that $d_{def}\left(u\right)=1$. Then $d_3\left(u\right)=0$, $d_{b2}\left(u\right)\le 1$ and $d_{g2}\left(u\right)=1$. Thus, $w^{\ast }\left(u\right)\ge 5-\frac{37}{12}-\frac{15}{24}-\frac{11}{24}-\frac{13}{24}=\frac{7}{24}$ by (1). Suppose that $d_{def}\left(u\right)=0$. Then $d_{b2}\left(u\right)\le d_{def}=0$, $d_{g2}\left(u\right)=2$ and $d_3\left(u\right)=3$. Thus, $w^{\ast }\left(u\right)\ge 5-\frac{37}{12}-2\times \frac{13}{24}-3\times \frac{13}{48}=\frac{1}{48}$ by (1).

Suppose that $d_2\left(u\right)=1$. If $d_{def}\left(u\right)=1$, then $s\left(u\right)=0$ and $d_{b2}\left(u\right)\le 1$ by Claim 3.3 (3) (4.1). Thus, $w^{\ast }\left(u\right)\ge 5-\frac{37}{12}-\frac{15}{24}-\frac{11}{24}-4\times \frac{1}{24}=\frac{2}{3}$. If $d_{def}\left(u\right)=0$, then $d_{b2}\left(u\right)\le d_{def}=0$, $d_{g2}\left(u\right)=1$ and $d_3\left(u\right)=4$. Thus, $w^{\ast }\left(u\right)\ge 5-\frac{37}{12}-\frac{13}{24}-4\times \frac{13}{48}=\frac{7}{24}$ by (1).

Suppose that $d_2\left(u\right)=0$. Then $w^{\ast }\left(u\right)\ge 5-\frac{37}{12}-5\times \frac{13}{48}=\frac{9}{16}$ by (1).

(4.2) $d=6$. According to Claim 3.3 (5), $d_{def}\left(u\right)\le 1$.

Suppose that $d_{def}\left(u\right)=1$. Then we have $d_{b2}\left(u\right)\le d_{def}\left(u\right)=1$. By Claim 3.3 (5.2), $d_{g2}\left(u\right)\le 1$. Thus, $w^{\ast }\left(u\right)\ge 6-\frac{37}{12}-\frac{15}{24}-\frac{11}{24}-\frac{13}{24}-4\times \frac{13}{48}=\frac{5}{24}$ by (1).

Suppose that $d_{def}\left(u\right)=0$. If $d_{g2}\left(u\right)\ge 5$, then $d_{3^{-}}\left(u\right)=5$. We have $d_{b2}\left(u\right)\le d_{def}\left(u\right)=0$. Thus, $w^{\ast }\left(u\right)\ge 6-\frac{37}{12}-5\times \frac{13}{24}=\frac{5}{24}$ by (1). If $d_{g2}\left(u\right)\le 4$, then $w^{\ast }\left(u\right)\ge 6-\frac{37}{12}-4\times \frac{13}{24}-2\times \frac{13}{48}=\frac{5}{24}$ by (1).

(4.3) $d\ge 7$. By Claim 3.3 (3), $d_{b2}\left(u\right)\le 1$.

(4.3.1) Suppose that $\Delta \left(G\right)\ge 13$.

Suppose that $7\le d\le \lceil \frac{\Delta \left(G\right)}{2}\rceil$. Then by Claim 3.4 (1) and (2), we have $d_2\left(u\right)\le d-1$ and $d_{def}\left(u\right)=0$. Then $d_{b2}\left(u\right)\le d_{def}\left(u\right)=0$ and $d_{g2}\left(u\right)\le d-1$. Thus, $w^{\ast }\left(u\right)\ge d-\frac{37}{12}-\left(d-1\right)\times \frac{13}{24}-\frac{13}{48}=\frac{11}{24}d-\frac{45}{16}>0$.

Suppose that $\lceil \frac{\Delta \left(G\right)}{2}\rceil +1\le d\le \Delta \left(G\right)-1$. Since $\Delta \left(G\right)\ge 13$, we have $d\ge 7$. Then by Claim 3.4 (3), we have $d_{def}\left(u\right)\le \lceil \frac{d}{2}\rceil -1$. If $d_{def}\left(u\right)=\lceil \frac{d}{2}\rceil -1$, then $d_{g2}\left(u\right)\le 1$, $d_{b2}\left(u\right)\le 1$. Thus, $\begin{array}{l}{w}^{\ast }\left(u\right)\ge d-\frac{37}{12}-\frac{15}{24}\left(\lceil \frac{d}{2}\rceil -1\right)-\frac{11}{24}-\frac{13}{24}-\frac{13}{48}\times \left(d-\lceil \frac{d}{2}\rceil \right)\\ =\frac{35}{48}d-\frac{17}{48}\lceil \frac{d}{2}\rceil -\frac{83}{24}\ge \frac{35}{48}d-\frac{17}{48}\left(\frac{d}{2}+\frac{1}{2}\right)-\frac{83}{24}=\frac{53}{96}d-\frac{349}{96}>0\end{array}$ by (1). If $d_{def}\left(u\right)\le \lceil \frac{d}{2}\rceil -2$, then $d_2\left(u\right)\le d-3$ and $d_{b2}\left(u\right)\le 1$. Thus, $\begin{array}{l}{w}^{\ast }\left(u\right)\ge d-\frac{37}{12}-\frac{15}{24}\left(\lceil \frac{d}{2}\rceil -2\right)-\frac{11}{24}-\frac{13}{24}\left(d-3-\lceil \frac{d}{2}\rceil +2\right)-\frac{13}{48}\times 3\\ =\frac{11}{24}d-\frac{1}{12}\lceil \frac{d}{2}\rceil -\frac{123}{48}\ge \frac{11}{24}d-\frac{1}{12}\left(\frac{d}{2}+\frac{1}{2}\right)-\frac{123}{48}=\frac{5}{12}d-\frac{125}{48}>0\end{array}$ by (1).

Suppose that $d=\Delta \left(G\right)\ge 13$. By Claim 3.5, we know $d_{def}\left(u\right)\le \Delta \left(G\right)-1$. If $d_{def}\left(u\right)=\Delta \left(G\right)-1$, then $d_{3^{-}}\left(u\right)=\Delta \left(G\right)-1$. Thus, $w^{\ast }\left(u\right)\ge \Delta \left(G\right)-\frac{37}{12}-\frac{15}{24}\left(\Delta \left(G\right)-1\right)-\frac{11}{24}=\frac{3}{8}\Delta \left(G\right)-\frac{35}{12}>0$ by (1). If $1\le d_{def}\left(u\right)\le \Delta \left(G\right)-2$, then by (1), we have $\begin{array}{l}{w}^{\ast }\left(u\right)\ge \Delta \left(G\right)-\frac{37}{12}-\frac{15}{24}{d}_{def}\left(u\right)-\frac{11}{24}{d}_{b2}\left(u\right)-\frac{13}{24}{d}_{g2}\left(u\right)-\frac{13}{48}{d}_3\left(u\right)\\ \ge \Delta \left(G\right)-\frac{37}{12}-\frac{15}{24}{d}_2\left(u\right)-\frac{11}{24}{d}_{b2}\left(u\right)-\frac{13}{48}\left(\Delta \left(G\right)-d_2\left(u\right)\right)\\ \ge \Delta \left(G\right)-\frac{37}{12}-\frac{15}{24}\left(\Delta \left(G\right)-2\right)-\frac{11}{24}-\frac{13}{48}\times 2=\frac{3}{8}\Delta \left(G\right)-\frac{17}{6}>0\end{array}$. If $d_{def}\left(u\right)=0$, then $w^{\ast }\left(u\right)\ge \Delta \left(G\right)-\frac{37}{12}-\frac{13}{24}\Delta \left(G\right)=\frac{11}{24}\Delta \left(G\right)-\frac{37}{12}>0$.

(4.3.1) Suppose that $8\le \Delta \left(G\right)\le 12$. We have $d\ge 7\ge \lceil \frac{\Delta \left(G\right)}{2}\rceil +1$. According to Claim 3.4 (3) and Claim 3.5, the derivation process is completely analogous to 4.3.1.

4. Conclusion

In this paper, we have studied neighbor sum distinguishing index of sparse graphs. However, there are still many graphs which are not covered here. So, for further research, we will consider the neighbor sum distinguishing edge coloring of planar graphs.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Zhang, Z.F., Liu, L.Z. and Wang, J.F. (2002) Adjacent Strong Edge Coloring of Graphs. Applied Mathematics Letters, 15, 623-626. https://doi.org/10.1016/S0893-9659(02)80015-5
[2]	Hatami, H. (2005) Δ + 200 Is a Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number. Journal of Combinatorial Theory Series B, 95, 246-256.
[3]	Akbari, S., Bidkhori, H. and Nosrati, N. (2006) r-Strong Edge Colorings of Graphs. Discrete Mathematics, 306, 3005-3010. https://doi.org/10.1016/j.disc.2004.12.027
[4]	Wang, W.F. and Wang, Y.Q. (2015) Some Bounds on the Neighbor-Distinguishing Index of Graphs. Discrete Mathematics, 338, 2006-2013. https://doi.org/10.1016/j.disc.2015.05.007
[5]	Flandrin, E., Marczyk, A. and Przybylo, J. (2013) Neighbor Sum Distinguishing Index. Graphs and Combinatorics, 29, 1329-1336. https://doi.org/10.1007/s00373-012-1191-x
[6]	Wang, G.H. and Yan, G.Y. (2014) An Improved Upper Bound for the Neighbor Sum Distinguishing Index of Graphs. Discrete Applied Mathematics, 175, 126-128. https://doi.org/10.1016/j.dam.2014.05.013
[7]	Bonamy, M. and Przybylo, J. (2017) On the Neighbor Sum Distinguishing Index of Planar Graphs. Journal of Graph Theory, 85, 669-690. https://doi.org/10.1002/jgt.22098
[8]	Dong, A.J., Wang, G.H. and Zhang, J.H. (2014) Neighbor Sum Distinguishing Edge Colorings of Graphs with Bounded Maximum Average Degree. Discrete Applied Mathematics, 166, 86-90. https://doi.org/10.1016/j.dam.2013.10.009
[9]	Gao, Y.P., Wang, G.H. and Wu, J.L. (2016) Neighbor Sum Distinguishing Edge Colorings of Graphs with Small Maximum Average Degree. Bulletin of the Malaysian Mathematical Sciences Society, 39, 247-256. https://doi.org/10.1007/s40840-015-0207-0
[10]	Hocquard, H. and Przybylo, J. (2017) On the Neighbor Sum Distinguishing Index of Graphs with Bounded Maximum Average Degree. Graphs and Combinatorics, 33, 1459-1471. https://doi.org/10.1007/s00373-017-1822-3
[11]	Qiu, B.J., Wang, J.H. and Liu, Y. (2018) Neighbor Sum Distinguishing Colorings of Graphs with Maximum Average Degree Less Than 37/12. Acta Mathematica Sinica, English Series, 34, 265-274. https://doi.org/10.1007/s10114-017-6491-x
[12]	Wang, J.H., Qiu, B.J. and Cai, J.S. (2020) Neighbor Sum Distinguishing Index of Sparse Graphs. Acta Mathematica Sinica, English Series, 36, 673-690. https://doi.org/10.1007/s10114-020-9027-8
[13]	Alon, N. (1999) Combinatorial Nullstellensatz. Combinatorics, Probability and Computing, 8, 7-29. https://doi.org/10.1017/S0963548398003411
[14]	Yu, X.W., Gao, Y.P. and Ding, L.H. (2018) Neighbor Sum Distinguishing Chromatic Index of Sparse Graphs Via the Combinatorial Nullstellensatz. Acta Mathematicae Applicatae Sinica, English Series, 34, 135-144. https://doi.org/10.1007/s10255-018-0731-4