Graphs that embedded in any fixed surfaces with sufficiently large maximum degree $\Delta$ is total-$(\Delta +1)$-colorable

1.   Introduction

We consider undirected, finite and simple graphs here. Definitions and notations not given here may be found in ^[1,2]. For a vertex $v$, we use $d_G(v)$, $N_G(v)$ (or simply, $d(v)$, $N(v)$) to denote the degree of $v$ and the neighborhood of $v$; furthermore, $\forall \; x\in V(G)\cup E(G)$, and we use $N_G^E(x)$ to denote the set that contains every edge that is incident with or adjacent to $x$. For a graph $G$ and a vertex set $S$, $G[S]$ is the subgraph induced by $S$. Surfaces in this paper are compact, connected, two-dimensional manifolds without boundary. All embeddings considered in this paper are two-cell embeddings. Let $S_k$ be the orientable surface with $k$ handles and let $N_k$ be the nonorientable surface with $k$ cross-caps. (Note that $k$ is the genus of the surfaces.)

The Euler characteristic of a surface $\Sigma$, denoted $c'(\Sigma)$, is defined by:

For a plane graph $G$, we use $V(G)$, $E(G)$, $\Delta(G)$, $\delta(G)$ and $F(G)$ to denote its vertex set, edge set, maximum degree, minimum degree and face set, respectively. A $k^+$-vertex ($k^-$-vertex) is a vertex $v$ with a degree of at least $k$ (at most $k$). Let $f$ be a face of $G$ and $d(f)$ means the number of vertices that is incident with $f$. Similarly, we can get the definitions of $k^+$-face and $k^-$-face. The boundary of a $t$-face $f$ is denoted by $\partial(f) = [v_1, \cdots, v_t]$, the set in which each vertex is incident with $f$ is denoted by $V(f)$.

A proper $l$-coloring of a graph $G$ is a mapping $c$ from $V(G)$ to the color set $\{1, 2, ..., l\}$ such that no two adjacent vertices are assigned the same color. We say $G$ is $l$-colorable if $G$ has a proper $l$-coloring. We use $c(v)$ to denote the color of the vertex $v$. The chromatic number $\chi(G)$ of $G$ is the smallest integer $k$ such that $G$ is $k$-colorable.

A total $k$-coloring of a graph $G$ is a mapping $\phi$ from $V(G)\cup E(G)$ to the set of colors $\{1, 2, ..., k\}$ such that $\phi(x)\neq \phi(y)$ for every pair of adjacent or incident elements $x, y\in V(G)\cup E(G)$. A graph $G$ is total-$k$-colorable if it has a total-$k$-coloring. The total chromatic number $\chi''(G)$ of $G$ is the smallest integer $k$ such that $G$ is total-$k$-colorable.

Let $L$ be a list assignment of $G$; a total coloring $c$ of $G$ is called a total-$L$-coloring of $G$ if $c(v)\in L(v)$ for any $v\in V(G)\cup E(G)$. A graph $G$ is total-$k$-choosable if $G$ has a total-$L$-coloring for any list $L$ with $|L(v)| = k$ for each $v\in V(G) \cup E(G)$. The total choice number of $G$, denoted by $\chi''_l(G)$, is the least integer $k$ such that $G$ is total-$k$-choosable.

Conjecture 1. Every graph satisfies $\chi''(G) \leq \Delta(G) +2$.

Conjecture 1 which is called the total coloring conjecture, was given by Behzad ^[3] and Vizing ^[15] independently and has only been confirmed for $\Delta\leq 5$ (See ^[9,10,11]).

For planar graphs, the bound $\chi''(G) \leq \Delta +2$ was first proved in 1987 by Borodin ^[4] for $\Delta \geq 11$, then for $\Delta \geq 9$ ^[5] and then the restriction on $\Delta$ was strengthened to $\Delta \geq 8$ by Jensen and Toft ^[8] and to $\Delta \geq 7$ by Sanders and Zhao ^[14].

Moreover, the bound $\chi''(G) = \Delta +1$ was first proved in 1987 by Borodin ^[4] for $\Delta \geq 16$, then for $\Delta \geq 14$ ^[5] and then the restriction on $\Delta$ was improved to 12 and 11 (Borodin, Kostochka and Woodall ^[6,7]), 10 (Wang ^[16]) and nine (Kowalik, Sereni and Škrekovski ^[12]). Wang et al. (2014) strengthened this result and got the following theorem.

Theorem 1.1. (Wang et al. ^[17]) Let $G$ be a graph that can be embedded in a surface $\Sigma$ of Euler characteristic $c'(\Sigma)\geq 0$. If $\Delta \geq 9$, then $\chi''(G)\leq \Delta +1$.

There are some open problems about total coloring.

Problem 1. (Sanders and Zhao ^[14]) Is every planar graph with $\Delta = 6$ total-8-colorable?

Problem 2. (Kowalik, Sereni, $\check{S}$krekovski ^[12]) What is the smallest $\Delta_0$, such that every planar graph with $\Delta(G) \geq \Delta_0$ satisfies $\chi''(G) = \Delta(G) +1$?

We notice that there are many results for total coloring of graphs that can be embedded in the surfaces of nonnegative Euler characteristics, but none for the surfaces of negative Euler characteristics. Therefore, we give the following conjecture.

Conjecture 2. Let $G$ be a graph that can be embedded in a surface $\Sigma$ of arbitrary Euler characteristic $c'(\Sigma)$, then there exists an integer $\Delta_0$ such that $\chi''(G) = \Delta(G) +1$ if $\Delta(G) \geq \Delta_0$.

In this paper, we prove the following theorem. For the convenience of the following part, let $\epsilon = \frac{1}{2} (5+\sqrt{49-24c'})$.

Theorem 1.2. Let $G$ be a graph that can be embedded in a surface $\Sigma$ of Euler characteristic $c' < 0$, then $\chi''(G) = \Delta(G) +1$ if $\Delta(G)\geq 8 \epsilon (2-c'+\epsilon)$.

Therefore, Conjecture 2 is the corollary of Theorems 1.1 and 1.2.

Let $S_k$ be the complete bipartite graph $K_{1, k}$. It is easy to verify that $\chi''(S_k) = k +1$. Let $G$ be a graph with $\Delta(G) = k$, then $S_k$ is a subgraph of $G$, which implies that $\chi''(G)\geq \chi''(S_k) = k +1 = \Delta(G) +1$. Therefore, we only need to prove $\chi''(G)\leq \Delta(G) +1$ in the following part.

2.   Preliminaries

Heawood proved the following analogue of the four color theorem for general surfaces.

Lemma 2.1. (Heawood ^[13]) Let $G$ be a graph that can be embedded in a surface $\Sigma$ of Euler characteristic $c'\neq 2$ ($\Sigma$ is not homeomorphic to the sphere), then $\chi(G)\leq \frac{1}{2} (7+\sqrt{49-24c'})$, and $G$ has a vertex of a degree less or equal to $\frac{1}{2} (5+\sqrt{49-24c'})$.

Lemma 2.1 implies that $G$ contains an $\epsilon^-$-vertex if $G$ can be embedded in a surface $\Sigma$ of Euler characteristic $c'$ ($c'\neq 2$ and $\epsilon = \frac{1}{2} (5+\sqrt{49-24c'})$).

In order to prove Theorem 1.2, we need the following lemma.

Lemma 2.2. (The Jordan curve theorem ^[2]) Any simple closed curve $C$ in the plane partitions the rest of the plane into two disjoint arcwise-connected open sets.

We have the following corollary by Lemma 2.2.

Corollary 1. If $C_1, C_2, ..., C_i$ are $i$ simple closed curves in the plane, then $C_1, C_2, ..., C_i$ partition the rest of the plane into at least $i+1$ disjoint arcwise-connected open sets.

Lemma 2.3. (^[1]) Let $S_k$ be the orientable surface with genus $g$, and $p$ be a point in $S_k$, then we can find $2g$ simple closed curves $\{C_1, C_2, ..., C_{2g}\}$, such that $p\in \bigcap_{i = 1}^{2g} C_i$ and $S_k \backslash (\bigcup_{i = 1}^{2g} C_i)$ is homeomorphic to the plane. (Note that these simple closed curves are not homotopic to each other, which impiles that these simple closed curves belong to different generators of the fundamental group $\pi(S_k, p)$ of $S_k$.)

Lemma 2.4. (^[1]) Let $N_k$ be the nonorientable surface with genus $g$, and $p$ be a point in $N_k$, then we can find $g$ simple closed curves $\{C_1, C_2, ..., C_{g}\}$, such that $p\in \bigcap_{i = 1}^{g} C_i$ and $N_k \backslash (\bigcup_{i = 1}^{g} C_i)$ is homeomorphic to the plane. (Note that these simple closed curves are not homotopic to each other, which impiles that these simple closed curves belong to different generators of the fundamental group $\pi(N_k, p)$ of $N_k$.)

We get the following corollary by Lemmas 2.3 and 2.4 and the definition of the Euler characteristic.

Corollary 2. Let $\Sigma$ be a surface of Euler characteristic $c'$, then we can find $2-c'$ simple closed curves $\{C_1, C_2, ..., C_{2-c'}\}$ such that these curves have a common point $p\in \bigcap_{i = 1}^{2-c'} C_i$ and $\Sigma \backslash (\bigcup_{i = 1}^{2-c'} C_i)$ is homeomorphic to the plane. (For example, four simple closed curves partition $S_2$ into a disc as shown in Figure 1.)

We get the following corollary by Corollaries 1 and 2.

Corollary 3. Let $\Sigma$ be a surface of Euler characteristic $c'$, then $(2-c'+i)$ simple closed curves $\{C_1, C_2, ..., C_{2-c'+i}\}$ in $\Sigma$ partition the rest of $\Sigma$ into at least $i+1$ disjoint arcwise-connected open sets ($i\in {\bf N}$).

Proof. We know that $2-c'$ simple closed curves can partition $\Sigma$ into a plane by Corollary 2 (note that $\Sigma$ remains arcwise-connected in this process. If we do not partition $\Sigma$ by the method in Corollary 2, $\Sigma$ will be divided into more pieces and we will get an easier proof), while the remaining $i$ curves further partition the plane into $i+1$ disjoint arcwise-connected open sets by Corollary 1. □

3.   Proof of Theorem 1.2

Let $G_0$ be a counterexample of Theorem 1.2, then $\Delta(G_0)\geq 8 \epsilon (2-c'+\epsilon)$ and $\chi''(G_0) > \Delta(G_0)+1$. Let $S = \{G : \Delta(G)\leq \Delta(G_0) = \Delta, \chi''(G) > \Delta(G_0) +1 = \Delta +1 \}$; the set isn't empty since $G_0\in S$. Let $G$ be the graph with the fewest edges in $S$. We assume that $G$ has been embedded in the surface $\Sigma$.

We prove Theorem 1.2 by constructing a simple graph $G'$, which can be embedded in $\Sigma$ from $G$ such that $\delta(G')\geq \epsilon +1$, that contradicts the fact that every simple graph that is embedded in surface $\Sigma$ has an $\epsilon ^-$-vertex.

3.1.   Definitions and notations

Let $[\Delta+1] = \{1, 2, ..., \Delta+1\}$ be a color set such that $G$ isn't total-$(\Delta+1)$-colorable. Let $c$ be a coloring of $G$; we use $c(x)$ to denote the color of $x$ for any $x\in V(G)\cup E(G)$. Let $X\subseteq V(G)\cup E(G)$ and define $c(X) = \{c(x):x\in X\}$.

Let $x$ be a cut vertex of $G$ and let the components of $G-x$ have vertex sets $V_1$, $V_2$, ..., $V_t$, then the subgraphs $G_i = G[V_i\cup \{x\}]$ are the $x$-components of $G$, where $i = 1, 2, \dots, t$.

If $P = v_1v_2...v_{x-1}v_x$ is a path with $V(P) = \{v_1, v_2, \dots, v_{x-1}, v_x\}$, then $v_1$ and $v_x$ are called the end vertices of $P$ and $v_i\in \{v_2, \dots, v_{x-1}\}$ is called an inner vertex of $P$.

The length of $P$, which is denoted by $|P|$, is the number of edges in $P$.

Let $v_1, v_x\in V(G)$, the distance between $v_1$ and $v_x$, denoted $d_G(v_1, v_x)$, be the length of the shortest path from $v_1$ to $v_x$.

A vertex $v$ is big if $d(v) \geq 4 \epsilon (2-c'+\epsilon) + 1$; otherwise, $v$ is small. The sets of big and small vertices of $G$ are denoted by $B(G)$ and $S(G)$, respectively.

As shown in Figure 2, let $C^*$ be a cycle of $G$ with the edge set $E(C^*)$. We can regard $C^*$ as a simple closed curve of the surface $\Sigma$. If $C$ partitions the rest of the surface $\Sigma$ into two disjoint arcwise-connected open sets, the two open sets into which $C^*$ partitions $\Sigma$ are called the interior and the exterior of $C^*$. We denote them by $int(C^*)$ and $ext(C^*)$, and their closures by $Int(C^*)$ and $Ext(C^*)$, respectively (thus, $Int(C^*)\cap Ext(C^*) = C^*$). Without loss of generality, we assume that $int(C^*)$ is homeomorphic to a disc. A vertex $v$ is an inner vertex of $C^*$ if $v\in int(C^*)$. A vertex $v$ is an outer vertex of $C^*$ if $v\in ext(C^*)$, and the sets of inner and outer vertices of $C^*$ are denoted by $V(int(C^*))$ and $V(ext(C^*))$, respectively.

3.2.   The properties of the minimal conterexample

Lemma 3.1. $G$ is connected, and $\delta(G)\geq2$.

Proof. Suppose to the contrary that $G$ has a 1-vertex $v$. By the choice of $G$, $G-v$ has a total-$(\Delta+1)$-coloring $c$. Let $N_G(v) = \{u\}$, then $uv$ can receive any color except for $c(u)$ and those colors in $c(N_G^E(u))$, so the number of forbidden colors of $uv$ is at most $1+(\Delta-1) = \Delta$. Similarly, the number of forbidden colors of $v$ is at most $1+1 = 2$. Therefore, we can extend $c$ to the whole graph $G$, a contradiction. □

Lemma 3.2. Let $\{u, v\}\subseteq B(G)$, then the number of 2-vertices, which are adjacent to both $u$ and $v$, is at most one.

Proof. Suppose to the contrary that there exists two vertices $w_1$ and $w_2$ such that $w_i$ is adjacent to both $u$ and $v$ and $d(w_i) = 2$ ($i\in \{1, 2\}$). By the choice of $G$, $G- \{w_1, w_2\}$ has a total-$(\Delta+1)$-coloring $c$, then the edge $uw_i$ can receive any color except for $c(u)$ and those colors in $c(N_G^E(u))$. The edge $vw_i$ can receive any color except for $c(v)$ and those colors in $c(N_G^E(v))$, then the number of forbidden colors of $e\in \{uw_1, uw_2, vw_1, vw_2\}$ is at most

which implies that the number of colors that can be used to color $e$ is at least two. By the fact that each even cycle is $2$-edge-choosable ^[2], we can color $\{uw_1, uw_2, vw_1, vw_2\}$ properly.

Finally, we easily recolor the $2$-vertices of this configuration and extend $c$ to the whole graph $G$, a contradiction. □

Lemma 3.3. Let $uv \in E(G)$. If $u\in S(G)$, then $v\in B(G)$. (This lemma implies that two small vertices cannot be adjacent.)

Proof. Suppose to the contrary that both $u\in S(G)$ and $v\in S(G)$. By the choice of $G$, $G-uv$ has a total-$(\Delta+1)$-coloring $c$, then the number of forbidden colors of $v$ is

Therefore $uv$ can receive any color except for $c(u)\cup c(v)$ and those colors in $c(N_G^E(u)\cup N_G^E(v))$, then the number of forbidden colors of $uv$ is

Thus, we can extend $c$ to the whole graph $G$, a contradiction.

□

Lemma 3.4. There is no cut vertex in $G$.

Proof. Suppose to the contrary that there exists a cut vertex $v$ in $G$ with $d(v)\leq \Delta$. Let $G_1$ be a $v$-component of $G$ and $G_2 = G[(V(G)\backslash V(G_1))\cup \{v\}]$. Let $N_{G_1}^E(v) = \{vv_1, vv_2, ..., vv_s\}$ and $N_{G_2}^E(v) = \{vv_{s+1}, vv_{s+2}, ..., vv_{d(v)}\}$. By the minimality of $G$, $G_1$ has a total-$(\Delta+1)$-coloring $c_1$ and $G_2$ has a total-$(\Delta+1)$-coloring $c_2$.

We notice that $\forall \; vv_i, vv_j \in N_{G_1}^E(v)$, $c_1(vv_i)\neq c_1(vv_j)$; $\forall \; vv_i, vv_j \in N_{G_2}^E(v)$, $c_2(vv_i)\neq c_2(vv_j)$. Let $X_j \subseteq V(G_1)\cup E(G_1)$ be the set that contains every vertex and edges that are colored by $j$ in $G_1$ for $j\in [\Delta+1]$, then for $vv_i\in \{vv_1, vv_2, ..., vv_s\}$, we exchange the colors of $X_{c_1(vv_i)}$ and $X_i$ such that $c(vv_i) = i$. We also exchange the colors of $X_{c_1(v)}$ and $X_{\Delta+1}$ such that $c_1(v) = \Delta+1$.

For $G_2$, we repeat this procedure such that $c(vv_j) = j$ for $vv_j\in \{vv_{s+1}, vv_{s+2}, ..., vv_{d(v)}\}$ (Since $G_1$ and $G_2$ are colored separately, this procedure cannot change the colors in $V(G_1)$). Note that $d(v)\leq \Delta$, which implies that there are at most $\Delta$ colors in $c(N_G^E(v))$. At last, we exchange the colors of $X_{c_2(v)}$ and $X_{\Delta+1}$ such that $c_2(v) = c_1(v) = \Delta+1$.

Thus, we can get a total coloring $c$ of $G$ from $c_1$ and $c_2$, a contradiction. □

Lemma 3.5. For each big vertex $b_1$ of $G$, there exists another big vertex $b_2$ such that the distance between $b_1$ and $b_2$ is at most two.

Proof. Suppose to the contrary that $\forall \; b\in B(G)$ with $b\neq b_1$, $d_G(b_1, b)\geq 3$. Let $P = b_1v_1v_2$ be a path, then $v_i\in S$ for $i\in \{1, 2\}$, which implies that a small vertex $v_1$ is adjacent to another small vertex $v_2$, contradicting the fact that a small vertex can only be adjacent to a big vertex in Lemma 3.3. □

3.3.   The definitions and notations of the link path

Remark. In the following figures, the black solid vertices means big vertices, the white hollow vertices means small 2-vertices and the gray vertices means small $3^+$- vertices. Note that there is no $1$-vertex in $V(G)$ by Lemma 3.1.

Now we give some definitions and notations that we will use in the following sections.

Let $P$ be a $b_1b_2$-path and $|P|\leq 2$. We say $P$ is a link path of $b_1$ and $b_2$ in $G$ if $b_i\in B(G)$ for $i\in \{1, 2\}$ and $v\in S(G)$ for $v\in V(P)\backslash \{b_1, b_2\}$.

Let $P$ be a link path of $b_1$ and $b_2$. We divide the link path $P$ into three types according to the length and the type of its inner vertices. The sets of Type 1-3 link paths of $G$ are denoted by $\mathscr{L}_1$-$\mathscr{L}_3$, respectively. Note that Lemmas 3.2, 3.3 and 3.5 ensure that the number of types of the link path is only three (As shown in Figure 3).

As shown in Figure 4, let $\{b_1, b_2, ..., b_x\}$ be the neighbors of a small $3^+$-vertex $u$ in clockwise order, then $b_i \in B(G)$ for $i\in \{1, 2, ..., x\}$. For all $b_i\in \{b_1, b_2, ..., b_x\}$, we say the link path $b_iub_{i+1}$ is a special-Type-3 link path of $b_i$ (or $b_{i+1}$), where $x+1\equiv 1 (mod\ x)$. For example, $b_1ub_2$ is a special-Type-3 link path and $b_1ub_3$ is not a special-Type-3 link path.

Let $b_1, b_2 \in B(G)$. We say $b_1$ is subadjacent to $b_2$ if there exists a Type-1, Type-2 or special-Type-3 link path $P$ of $b_1$ and $b_2$.

Assume that both $P_1$ and $P_2$ are link paths of $b_1$ and $b_2$. Let $C^* = G[V(P_1)\cup V(P_2)]$. We assume that $C^*$ partitions the surface $\Sigma$ into two disjoint arcwise-connected open sets. We say $P_1$ is adjacent to $P_2$ if $V(int(C^*)) = \phi$ or $V(ext(C^*)) = \phi$.

Let $\mathscr{P} = \{P_1, P_2, \dots, P_{m-1}, P_m\}$ be a sequence of the link paths of $b_1$ and $b_2$ and $\mathscr{P}$ is called an ordered sequence of the link paths of $b_1$ and $b_2$ if $P_i$ is adjacent to $P_{i+1}$ for $i\in \{1, 2, \dots, m-1\}$. We say $\mathscr{P}$ is a maximal ordered sequence of the link paths of $b_1$ and $b_2$ if, for any ordered sequence of the link paths $\mathscr{P}' = \{P_{x_1}, P_{x_2}, \dots, P_{x_n}\}$ that satisfy $\mathscr{P} \subseteq \mathscr{P}'$, we have $\mathscr{P}' = \mathscr{P}$.

According to the definitions and notations above, we give the following lemma about the link path.

Lemma 3.6. Let $b_1$ and $b_2$ be any two big vertices of $G$ and $\mathscr{P} = \{P_1, P_2, \dots, P_r\}$ be a maximal ordered sequence of the link paths of $b_1$ and $b_2$, then $r\leq 4$ (furthermore, if $\mathscr{P}$ only contains Type-3 link paths of $b_1$ and $b_2$, then $r\leq 2$).

Proof. As shown in Figure 5, the number of Type-1 link paths of $b_1$ and $b_2$ is at most one since $G$ is a simple graph; the number of Type-2 link paths of $b_1$ and $b_2$ is at most one by Lemma 3.2.

Now we prove that the number of Type-3 link paths of $b_1$ and $b_2$ in $\mathscr{P}$ is at most two. Suppose to the contrary that there are three Type-3 link paths of $b_1$ and $b_2$ in $\mathscr{P}$, which are denoted by $\{b_1v_1b_2, b_1v_2b_2, b_1v_3b_2\}$.

Let $C_1 = b_1v_1b_2v_2b_1$, $C_2 = b_1v_2b_2v_3b_1$. By the definition of the maximal ordered sequence of the link paths, we know that both $int(C_1)$ and $int(C_2)$ are homeomorphic to discs. Furthermore, $b_1v_2b_2$ is the common boundary of $int(C_1)$ and $int(C_2)$. Now, we can infer that the degree of $v_2$ must be two since $b_1v_2b_2$is adjacent to both $b_1v_1b_2$ and $b_1v_3b_2$, contradicting the fact that $b_1v_2b_2$ is a Type-3 link path.

Therefore, $r\leq 4$. □

In the following part, we will construct a simple graph $G'$ that can be embedded in $\Sigma$ from $G$ such that $V(G') = B(G)$ and $\delta(G')\geq \epsilon +1$, which contradicts the fact that every simple graph embedded in surface $\Sigma$ has an $\epsilon ^-$-vertex. Thus, the proof is completed.

Remark 1. We assume that $G$ has been embedded in $\Sigma$ and the position of each vertex in $B(G)$ does not change in the following part.

3.4.   Construction process of $G'$

Now, we are ready to construct a simple graph $G'$ from $G$ such that $V(G') = B(G)$.

The construction process is listed below. Note that $V(G_0) = V(G_1) = V(G_2) = B(G)$ in the following part:

First, we assume that $G_0$ is an empty graph such that $V(G_0) = B(G)$, then we add edges to the empty graph $G_0$ one by one by the following two steps.

The graph obtained after (S1) is denoted by $G_1$

(S1). If there exists a Type-1 or Type-2 link path of $b_1$ and $b_2$ in $G$, we choose an arbitrary Type-1 or Type-2 link path $P$ then add an edge $b_1b_2$ in $G_0$. Make sure the edge $b_1b_2$ entirely overlaps with $P$.

Remark 2. It is obvious that $G_1$ is a graph that can be embedded in $\Sigma$ since each edge of $G_1$ corresponds to a link path in graph $G$.

The graph that is obtained after (S1) and (S2) is denoted by $G_2$. As shown in Figure 6, the real lines stand for the edges in $G$ while the dotted lines stand for the edges in $G_2$.

(S2). Let $u'\in V(G)\backslash B(G)$ and $d(u') = x$, $N_{G}(u') = \{b_1, b_2, \dots, b_x\}$ in clockwise order and note that $b_i\in B(G)$ for $i\in \{1, 2, \dots, x\}$. For any $i\in \{1, 2, \dots, x\}$, let $P_i' = b_iu'b_{i+1}$ where $x+1\equiv 1 (mod\ x)$, then $P_i'$ is a link path of $b_i$ and $b_{i+1}$ in $G$. Add an edge $b_ib_{i+1}$ in $G_1$ such that the edge $b_ib_{i+1}$ is as close as possible to $P_i'$ (only close, not overlapping).

Remark 3. It is obvious that the edges that are added in (S2) only intersect at their ends, and each edge that is added in (S2) only intersects with the edges that are added in (S1) at their ends. Thus, we know that $G_2$ can be embedded in $\Sigma$.

Let $G'$ be the simple graph of $G_2$ (with no loops or parallel edges). Next we will prove that $\delta (G')\geq \epsilon +1$ and get a contradiction.

3.5.   The properties of $G'$

Claim 3.1. If there exists a path $P$ such that $P$ is a Type-1 or Type-2 link path of $b_1$ and $b_2$ in $G$, then $b_1$ is adjacent to $b_2$ in $G'$.

Proof. It is easy to verify this claim by (S1). □

Claim 3.2. If there exists a path $P$ such that $P$ is a Type-3 link path of $b_1$ and $b_2$ in $G$, let $P = b_1u'b_2$, then there exist two vertices $b, \; b^*\in N_{G}(u')$ such that $\{b, b^*\}\subseteq N_{G'}(b_1)$.

Proof. It is easy to verify this claim by (S2). (Note that $b_1u'b$ and $b_iu'b^*$ are special-Type-3 link paths. For example, as shown in Figure 6, $\{b_2, b_x\}\subseteq N_{G'}(b_1)$.) □

Lemma 3.7. $\delta (G')\geq \epsilon +1$.

Proof. Note that $V(G') = B(G)$. Let $b$ be an arbitrary vertex in $V(G')$. Let $b_i\in B(G)$. Recall that $b$ is subadjacent to $b_i$ in $G$ if there exists a Type-1, Type-2 or special-Type-3 link path $P$ of $b$ and $b_i$ in $G$.

Case 1. If $b$ is subadjacent to at least $\epsilon +1$ big vertices in $G$, it is easy to verify that $d_{G'}(b)\geq \epsilon +1$ by Claims 3.1 and 3.2.

Case 2. If $b$ is subadjacent to at most $t$ ($t\leq \epsilon$) big vertices $\{b_1, b_2, ..., b_t\}$ in $G$, then there exists $b' \in \{b_1, b_2, ..., b_t\}$ such that the number of link paths of $b$ and $b'$ in $G$ is at least $\lceil \frac{4 \epsilon (2-c'+\epsilon) + 1}{t} \rceil \geq 4(2-c'+\epsilon)$ by pigeonhole principle. The number of maximal ordered sequence of the link paths of $b$ and $b'$ is at least $(2-c'+\epsilon)$ by Lemma 3.6. We assume that the number of maximal ordered sequences of the link paths of $b$ and $b'$ is $(2-c'+\epsilon)$, otherwise we can get an easier proof.

Let $\mathscr{P}_1, \mathscr{P}_2, ..., \mathscr{P}_{2-c'+\epsilon}$ be the maximal ordered sequence of the link paths of $b$ and $b'$, then $\forall \; \mathscr{P}_i \in \{\mathscr{P}_1, \mathscr{P}_2, ..., \mathscr{P}_{2-c'+\epsilon}\}$. We regard $\mathscr{P}_i$ as a new path $P_i'$ as shown in Figure 7 (the gray region is a new path of $bb'$), then $(2-c'+\epsilon)$ paths $P_1', P_2', ..., P_{2-c'+\epsilon}'$ can form $(2-c'+\epsilon-1)$ simple closed curves $C_1, C_2, ..., C_{2-c'+\epsilon-1}$ in $\Sigma$. By Corollary 3, we know that $(2-c'+\epsilon-1)$ simple closed curves partition $\Sigma$ into at least $\epsilon$ disjoint arcwise-connected open sets. Without loss of generality, let $\Sigma\backslash (\bigcup_{i = 1}^{2-c'+\epsilon-1} C_i) = D_1\cup D_2\cup...\cup D_{\epsilon}$, where $D_i$ is the arcwise-connected open set and they disjoint with each other for $D_i\in \{D_1, D_2, ..., D_{\epsilon}\}$. In the following part, we prove that $b$ is adjacent to at least $\epsilon+1$ vertices in $G'$.

Subcase 2.1. If $\forall \; D_i\in \{D_1, D_2, ..., D_{\epsilon}\}$, there exists a Type-3 link path $P_i$ of $b$ and $b'$ such that $P_i$ is on the boundary of $D_i$. Let $P_i = bub'$, then $u\in S(G)$ and $d(u)\geq 3$. It is obvious that there is neither a $b$-component nor a $b'$-component in $D_i$ by Lemma 3.4 (as shown in Figure 8(1), the white line means a vertex with uncertain degree). Recall that two small vertices cannot be adjacent by Lemma 3.3, which implies that there exists $b_i\in D_i$ such that $b_i\in N_G(u)$ and $b_i$ is subadjacent to $b$ in $G$ (as shown in Figure 8(2)). It is easy to verify that $b_i$ is adjacent to $b$ in $G'$ by Claim 3.2.

Therefore, for all $D_i\in \{D_1, D_2, ..., D_{\epsilon}\}$, there exists $b_i\in D_i$ ($b_i\neq b'$) such that $b_i$ is a big vertex and $b_i$ is adjacent to $b$ in $G'$, and it is obvious that $b'$ is adjacent to $b$ in $G'$. Thus, we know that $d_{G'}(b)\geq \epsilon+1$.

Subcase 2.2. If there exists $D_i\in \{D_1, D_2, ..., D_{\epsilon}\}$ such that the boundary of $D_i$ contains either Type-1 or Type-2 link paths of $b$ and $b'$, note that the number of Type-1 (or Type-2) link paths of $b$ and $b'$ is at most one by Lemma 3.2, which implies that the boundary of $D_i$ contains exactly one Type-1 link path and one Type-2 link path of $b$ and $b'$. Recall that the number of link paths of $b$ and $b'$ in $G$ is at least $4(2-c'+\epsilon)$, then the number of maximal ordered sequence of the link paths of $b$ and $b'$ is at least $\lceil \frac{4 (2-c'+\epsilon)-1-1}{2} \rceil \geq (2-c'+\epsilon)+1$.

Now $(2-c'+\epsilon)+1$ maximal ordered sequence of the link paths of $b$ and $b'$ can form $(2-c'+\epsilon)+1$ paths, $(2-c'+\epsilon)+1$ paths can form $(2-c'+\epsilon)$ simple closed curves and $(2-c'+\epsilon)$ simple closed curves partition $\Sigma$ into at least $\epsilon+1$ disjoint arcwise-connected open sets $\{D_1', D_2', ..., D_{\epsilon+1}'\}$, then $\forall \; D_j'\in \{D_1', D_2', ..., D_{\epsilon+1}'\} \backslash \{D_i\}$, we can find a Type-3 link path $P_j'$ of $b$ and $b'$ such that $P_j'$ is on the boundary of $D_j'$ (since $D_j'\neq D_i$). Let $P_j' = bu'b'$, then $u'\in S(G)$ and $d(u')\geq 3$, which implies that there exists $b_j'\in D_j'$ such that $b_j'\in N_G(u')$ and $b_j'$ is subadjacent to $b$. It is easy to verify that $b_j'$ is adjacent to $b$ in $G'$ by Claim 3.2.

Therefore, for all $\forall \; D_j'\in \{D_1', D_2', ..., D_{\epsilon+1}'\} \backslash \{D_i\}$, there exists $b_j'\in D_j'$ ($b_j'\neq b'$) such that $b_j'$ is a big vertex and $b_j'$ is adjacent to $b$ in $G'$, and it is obvious that $b'$ is adjacent to $b$ in $G'$. Thus, we know that $d_{G'}(b)\geq \epsilon+1$. □

Now, we get a simple graph $G'$ that can be embedded in $\Sigma$ such that $V(G') = B(G)$ and $\delta(G')\geq \epsilon +1$, which contradicts the fact that every simple graph embedded in $\Sigma$ has an $\epsilon^-$-vertex. The proof is completed.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Supported by the Natural Science Foundation of China, Grant No.11871377.

Conflict of interest

The authors declare that they have no conflicts of interest regarding the publication of this paper.