# Semialgebraic Calderón-Zygmund theorem on regularization of the distance
function

Beata Kocel-Cynk, Wiesław Pawłucki and Anna Valette  (B. Kocel-Cynk) Instytut
Matematyki Politechniki Krakowskiej, ul. Warszawska 24, 31-155 Kraków, Poland
<EMAIL_ADDRESS>(W. Pawłucki) Instytut Matematyki Uniwersytetu
Jagiellońskiego, ul. Prof. St. Łojasiewicza 6, 30-048 Kraków, Poland
<EMAIL_ADDRESS>(A. Valette) Katedra Teorii Optymalizacji i
Sterowania Uniwersytetu Jagiellońskiego, ul. Prof. St. Łojasiewicza 6, 30-048
Kraków, Poland<EMAIL_ADDRESS>
(Date: 28 November, 2023 Anna Valette was partially supported by Narodowe
Centrum Nauki (Poland); grant no. 2021/43/B/ST1/02359)

###### Abstract.

We prove that, for any closed semialgebraic subset $W$ of $\mathbb{R}^{n}$ and
for any positive integer $p$, there exists a Nash function
$f:\mathbb{R}^{n}\setminus W\longrightarrow(0,\infty)$ which is equivalent to
the distance function from $W$ and at the same time it is
$\Lambda_{p}$-regular in the sense that $|D^{\alpha}f(x)|\leq
Cd(x,W)^{1-|\alpha|}$, for each $x\in\mathbb{R}^{n}\setminus W$ and each
$\alpha\in\mathbb{N}^{n}$ such that $1\leq|\alpha|\leq p$, where $C$ is a
positive constant. In particular, $f$ is Lipschitz. Some applications of this
result are given.

###### Key words and phrases:

Semialgebraic set, semialgebraic mapping, Nash approximation,
$\Lambda_{p}$-regular mapping

###### 1991 Mathematics Subject Classification:

Primary 14P20. Secondary 57R35, 14P10, 32B20

##  1\. Introduction

The Calderón-Zygmund theorem on regularization of the distance function
asserts that for any closed subset $W\subset\mathbb{R}^{n}$ there exists a
$\mathcal{C}^{\infty}$-function $f:\mathbb{R}^{n}\setminus
W\longrightarrow(0,\infty)$ equivalent to the distance function from $W$; i.e.
there exists a constant $A>0$ such that

$A^{-1}d(x,W)\leq f(x)\leq Ad(x,W),\quad\text{for each
$x\in\mathbb{R}^{n}\setminus W$}$

and, moreover, there are constants $B_{\alpha}>0$ $(\alpha\in\mathbb{N}^{n})$,
such that

$|D^{\alpha}f(x)|\leq B_{\alpha}(d(x,W))^{1-|\alpha|},\quad\text{for each
$x\in\mathbb{R}^{n}\setminus W$ and each $\alpha\in\mathbb{N}^{n}$}.$

It was introduced in connection with a study of elliptic partial differential
equations (cf. [2]) and appears a useful tool in analysis (cf. [14, Chapter
VI]).

Since semialgebraic geometry (cf. [1]) together with its generalizations
(subanalytic geometry (cf.[13]), o-minimal geometry (cf.[3])) appears very
valuable in areas of applied mathematics such as robotics and CAD, it was an
interesting open question if the Calderón-Zygmund theorem has a counterpart in
the semialgebraic category. Our aim is to give a positive answer; namely, we
prove the following.

######  Theorem 1.1.

For any closed semialgebraic subset $W$ of $\mathbb{R}^{n}$ and any positive
integer $p$, there exists a Nash function $($i.e. semialgebraic and
$\mathcal{C}^{\infty}$$)$ $f:\mathbb{R}^{n}\setminus
W\longrightarrow(0,\infty)$ and positive constants $A,B$ such that, for each
$x\in\mathbb{R}^{n}\setminus W$

(1.1) $A^{-1}d(x,W)\leq f(x)\leq Ad(x,W),$

and

(1.2) $|D^{\alpha}f(x)|\leq B(d(x,W))^{1-|\alpha|},\,\text{where
$\alpha\in\mathbb{N}^{n}$ and $|\alpha|\leq p$}.$

The proof of Theorem 1.1 is based on $\Lambda_{p}$-regular stratifications
(see Section 2) introduced by the second author with Krzysztof Kurdyka in [7],
in connection with a subanalytic version of the Whitney extension theorem,
combined with a version of the Efroymson-Shiota approximation theorem, cited
below (see Theorem 1.4). In fact, we will need the following generalization of
the notion of $\Lambda_{p}$-regular function considered in [7].

######  Definition 1.2.

Let $W\subset\mathbb{R}^{n}$ be a closed semialgebraic subset, let
$p,k\in\mathbb{Z}$, where $p>0$. Let $\varOmega\subset\mathbb{R}^{n}$ be an
open semialgebraic subset disjoint from $W$. We say that a semialgebraic
$\mathcal{C}^{p}$-function $f:\varOmega\longrightarrow\mathbb{R}$ is
$\Lambda^{k}_{p}(W)$-_regular_ if there exists a constant $M>0$ such that

$|D^{\alpha}f(x)|\leq Md(x,W)^{k-|\alpha|},$

for each $x\in\varOmega$ and $\alpha\in\mathbb{N}^{n}$ such that
$1\leq|\alpha|\leq p$.

When $f$ is $\Lambda^{1}_{p}(\partial\varOmega)$-regular we say that $f$ is
$\Lambda_{p}$-_regular_ (as in [7]).

Our main effort in this paper is focused on proving the following
approximation theorem for Lipschitz functions (notice that the distance
function is a particular case).

######  Theorem 1.3.

Let $W\subset\mathbb{R}^{n}$ be any closed semialgebraic subset and let $p$ be
a positive integer. Let $g:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ be any
semialgebraic Lipschitz function vanishing on $W$.
Then, for any $\kappa>0$, there exists a $\Lambda^{1}_{p}(W)$-regular function
$f:\mathbb{R}^{n}\setminus W\longrightarrow\mathbb{R}$ such that, for each
$x\in\mathbb{R}^{n}\setminus W$,

$|f(x)-g(x)|\leq\kappa d(x,W).$

The proof of Theorem 1.3 is based on a special $\Lambda^{0}_{p}(W)$ partition
of unity, which we establish in Section 3, and we believe has its own
interest. It is also worth noting that Theorem 1.3 with the given proof holds
true in the setting of any o-minimal structure on the field of real numbers
$\mathbb{R}$.

We will use a special case of the Efroymson-Shiota approximation theorem. To
quote this, we first recall the definition of the _semialgebraic
$\mathcal{C}^{p}$-topology_. Let $G$ and $H$ be open semialgebraic subsets in
$\mathbb{R}^{n}$ and in $\mathbb{R}^{m}$, respectively. Let $p$ be a non-
negative integer. Denote by $\mathcal{N}^{p}(G,H)$ the set of all
semialgebraic $\mathcal{C}^{p}$-mappings from $G$ to $H$; i.e.
$\mathcal{C}^{p}$-mappings with semialgebraic graphs. Let
$f\in\mathcal{N}^{p}(G,H)$. Then basic neighborhoods of $f$ in
$\mathcal{N}^{p}(G,H)$ in the semialgebraic $\mathcal{C}^{p}$-topology are of
the form

$U_{\varepsilon}(f)=\\{h\in\mathcal{N}^{p}(G,H):\,|D^{\alpha}f(x)-D^{\alpha}h(x)|\leq\varepsilon(x),\phantom{..................}$

whenever $\alpha\in\mathbb{N}^{n}$, $|\alpha|\leq p$ and $x\in G$}, where
$\varepsilon:G\longrightarrow(0,\infty)$ is any semialgebraic positive
continuous function on $G$.

######  Theorem 1.4 (Efroymson-Shiota approximation theorem).

Nash mappings $($i.e. semialgebraic and $\mathcal{C}^{\infty}$$)$ from $G$ to
$H$ are dense in $\mathcal{N}^{p}(G,H)$ in the semialgebraic
$\mathcal{C}^{p}$-topology.

This deep result originating in the paper of Efroymson [4] for $p=0$ (compare
also [11]), was completed and generalized, for any non-negative $p$, by Shiota
in [12]. In fact, Shiota’s formulation is stronger than Theorem 1.4; namely,
the sets $G$ and $H$ above can be any Nash submanifolds embedded in
$\mathbb{R}^{n}$ and in $\mathbb{R}^{m}$, respectively.

It is now a simple matter to see that Theorem 1.1 is a consequence of first
applying Theorem 1.3, where we put $g(x)=d(x,W)$, followed by Theorem 1.4,
applied to a resulting $f$. Hence, the rest of our paper is devoted to proving
Theorem 1.3.

##  2\. $\Lambda_{p}$-regular cells

We recall after [7] (see also [8], [9] and [10]), the definition of
$\Lambda_{p}$-regular cells in $\mathbb{R}^{n}$.

######  Definition 2.1.

Let $p$ be a positive integer. We say that $S$ is an _open
$\Lambda_{p}$-regular cell_ in $\mathbb{R}^{n}$ if

(2.1) $S$ is any open interval in $\mathbb{R}$, when $n=1$; (2.2)
$S=\\{(x^{\prime},x_{n}):x^{\prime}\in
T,\psi_{1}(x^{\prime})<x_{n}<\psi_{2}(x^{\prime})\\},$

where $x^{\prime}=(x_{1},\dots,x_{n-1})$, $T$ is an open $\Lambda_{p}$-regular
cell in $\mathbb{R}^{n-1}$ and every $\psi_{i}$ $(i\in\\{1,2\\})$ is either a
semialgebraic $\Lambda_{p}$-regular function on $T$ (see Definition 1.2) with
values in $\mathbb{R}$, or identically equal to $-\infty$, or identically
equal to $+\infty$, and $\psi_{1}(x^{\prime})<\psi_{2}(x^{\prime})$, for each
$x^{\prime}\in T$, when $n>1$.

Extending the above definition, we say that $S$ is an _$m$ -dimensional
$\Lambda_{p}$-regular cell_ in $\mathbb{R}^{n}$, where
$m\in\\{0,\dots,n-1\\}$, if

(2.3) $S=\\{(u,w):\,u\in T,w=\varphi(u)\\},$

where $u=(x_{1},\dots,x_{m})$, $w=(x_{m+1},\dots,x_{n})$, $T$ is an open
$\Lambda_{p}$-regular cell in $\mathbb{R}^{m}$, and
$\varphi:T\longrightarrow\mathbb{R}^{n-m}$ is a semialgebraic
$\Lambda_{p}$-regular mapping.

######  Remark 2.2.

One easily checks by induction that every $\Lambda_{p}$-regular cell is
Lipschitz in the sense that each of the functions $\psi_{i}$ in (2.2), if
finite, as well as the mapping $\varphi$ in (2.3), are Lipschitz. Besides,
every $\Lambda_{p}$-regular cell in $\mathbb{R}^{n}$ is a semialgebraic
connected $\mathcal{C}^{p}$-submanifold of $\mathbb{R}^{n}$.

######  Definition 2.3.

Let us recall that a (_semialgebraic_) $\mathcal{C}^{p}$-_stratification_ of a
(semialgebraic) subset $E$ of $\mathbb{R}^{n}$ is a finite decomposition
$\mathcal{S}$ of $E$ into (semialgebraic) connected
$\mathcal{C}^{p}$-submanifolds of $\mathbb{R}^{n}$, called _strata_ , such
that for each stratum $S\in\mathcal{S}$, its _boundary_ in $E$; i.e.
$\partial_{E}S:=(\overline{S}\setminus S)\cap E$ is the union of some strata
of dimensions $<\dim S$. If $A_{1},\dots,A_{k}$ $(k\in\mathbb{N})$ are subsets
of $E$, we call a stratification $\mathcal{S}$ _compatible with the subsets
$A_{1},\dots,A_{k}$_, if each $A_{j}$ is a union of some strata.

The following proposition is crucial in the proof of Theorem 2.6 below, which
is a fundamental theorem on $\Lambda_{p}$-stratifications.

######  Proposition 2.4 ([8, Corollary to Proposition 4 ]).

Let $\varPhi:\varOmega\longrightarrow\mathbb{R}$ be a semialgebraic
$\mathcal{C}^{1}$-function defined on a semialgebraic open subset $\varOmega$
of $\mathbb{R}^{n}$ such that

$\Big{|}\frac{\partial\varPhi}{\partial x_{j}}\Big{|}\leq
M\qquad(j\in\\{1,\dots,n\\}),$

where $M$ is a positive constant, and let $p$ be a positive integer. Then
there exists a closed semialgebraic nowhere dense subset $Z$ of $\varOmega$
such that $\Phi$ is of class $\mathcal{C}^{p}$ on $\varOmega\setminus Z$ and

$|D^{\alpha}\varPhi(u)|\leq C(n,p)Md(u,Z\cup\partial\Omega),$

whenever $u\in\varOmega\setminus Z$, $\alpha\in\mathbb{N}^{n}$,
$1\leq|\alpha|\leq p$, and where $C(n,p)$ is a positive integer depending only
on $n$ and $p$.

######  Remark 2.5.

If $\varPhi:\varOmega\longrightarrow\mathbb{R}$ is a semialgebraic Lipschitz
function with a constant $M$ defined on a semialgebraic open subset
$\varOmega$ of $\mathbb{R}^{n}$, then there exists a closed semialgebraic
nowhere dense subset $Z^{\prime}$ of $\varOmega$ such that $\varphi$ is of
class $\mathcal{C}^{1}$ on $\varOmega\setminus Z^{\prime}$ and

$\Big{|}\frac{\partial\varPhi}{\partial x_{j}}\Big{|}\leq
M\quad\text{on}\quad\varOmega\setminus Z^{\prime}.$

######  Theorem 2.6.

Let $p$ be a positive integer. Given any finite number $A_{1},\dots,A_{k}$ of
semialgebraic subsets of a semialgebraic subset $E$ of $\mathbb{R}^{n}$, and a
semialgebraic Lipschitz mapping $g:E\longrightarrow\mathbb{R}^{d}$, where
$d\in\mathbb{N}$, there exists a semialgebraic
$\mathcal{C}^{p}$-stratification $\mathcal{S}$ of $E$ compatible with sets
$A_{1},\dots,A_{k}$ and such that every stratum $S\in\mathcal{S}$, after an
orthogonal linear change of coordinates111By [10], permutations of coordinates
$x_{1},\dots,x_{n}$ suffice. in $\mathbb{R}^{n}$, is a $\Lambda_{p}$-regular
cell in $\mathbb{R}^{n}$ and if $S$ is open then $g|S$ is
$\Lambda_{p}$-regular, while in the case $\dim S=m<n$, when $S$ is of the form
$(2.3)$,

(2.4) the mapping $T\ni u\longmapsto g(u,\varphi(u))\in\mathbb{R}^{d}$ is
$\Lambda_{p}$-regular.

###### Proof.

The proof follows the inductive procedure as in the proof of Proposition 4 in
[7] (or that of Theorem 3 in [8]); i.e. the induction on $\dim E$. The only
difference is that, at each inductive step, constructing strata of dimension
$<m$, we have to take into account the Lipschitz mapping $g$ restricted to
strata of dimension $m$ making use of Remark 2.5 and Proposition 2.4. ∎

##  3\. A partition of unity

######  Definition 3.1.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let
$Z\subset\mathbb{R}^{n}\setminus W$. We will consider the following open
neighborhoods of $Z$ in $\mathbb{R}^{n}$

$G_{\eta}(Z,W):=\\{x\in\mathbb{R}^{n}\setminus W:\,d(x,Z)<\eta d(x,W)\\},$

where $\eta>0$. (We adopt the convention that $d(x,\emptyset)=\infty$.)

The main result of this section is the following theorem on
$\Lambda^{0}_{p}(W)$-partition of unity, which can be considered as a
semialgebraic counterpart of the famous Whitney partition of unity.

######  Theorem 3.2.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let
$U_{1},\dots,U_{s}$ be any finite covering of $\mathbb{R}^{n}\setminus W$ by
semialgebraic subsets. Then, for any positive integer $p$ and any $\eta>0$,
there exist $\Lambda^{0}_{p}(W)$-regular functions
$\omega_{i}:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$
$(i\in\\{1,\dots,s\\})$ such that $\omega_{1}+\dots+\omega_{s}\equiv 1$ on
$\mathbb{R}^{n}\setminus W$ and $\rm supp$$\omega_{i}\subset
G_{\eta}(U_{i},W)$ $(i\in\\{1,\dots,s\\})$, where $\rm supp$$\omega_{i}$
denotes the closure of $\\{x\in\mathbb{R}^{n}\setminus W:\,\omega_{i}(x)\neq
0\\}$ in $\mathbb{R}^{n}\setminus W$.

Before starting the proof of Theorem 3.2, we will prove the following two
simple lemmas.

######  Lemma 3.3.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let
$\varOmega$ be an open semialgebraic subset of $\mathbb{R}^{n}$ disjoint from
$W$. If $f:\varOmega\longrightarrow\mathbb{R}$ is a
$\Lambda^{k}_{p}(W)$-regular function and
$g:\varOmega\longrightarrow\mathbb{R}$ is a $\Lambda^{l}_{p}(W)$-regular
function, where $k,l,p\in\mathbb{Z}$, $p>0$ and if there exists $A>0$ such
that $|f(x)|\leq Ad(x,W)^{k}$ and $|g(x)|\leq Ad(x,W)^{l}$, for each
$x\in\varOmega$, then the function $fg$ is $\Lambda^{k+l}_{p}(W)$-regular.

###### Proof.

Directly from the Leibnitz formula. ∎

######  Lemma 3.4.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let
$\varOmega$ be an open semialgebraic subset of $\mathbb{R}^{n}$ disjoint from
$W$. If $f:\varOmega\longrightarrow\mathbb{R}$ is a
$\Lambda^{k}_{p}(W)$-regular function, where $k,p\in\mathbb{Z}$, $p>0$, and
there exists $a>0$ such that $ad(x,W)^{k}\leq|f(x)|$, for each
$x\in\varOmega$, then the function $1/f$ is $\Lambda^{-k}_{p}(W)$-regular.

###### Proof.

Observe that $D^{\alpha}(1/f)$ $(\alpha\in\mathbb{N}^{n}\setminus\\{0\\})$, is
a linear combination, with integral coefficients independent of $f$, of
products of the form

$f^{-(m+1)}(D^{\beta_{1}}f)\dots(D^{\beta_{m}}f),$

where $1\leq m\leq|\alpha|$,
$\beta_{1},\dots,\beta_{m}\in\mathbb{N}^{n}\setminus\\{0\\}$, and
$\sum_{i=1}^{m}\beta_{i}=\alpha$. Hence, we get

$|D^{\alpha}(1/f)(x))|\leq Cd(x,W)^{-k(m+1)}d(x,W)^{k-|\beta_{1}|}\dots
d(x,W)^{k-|\beta_{m}|}=$ $Cd(x,W)^{-k-|\alpha|},$

where $C>0$. ∎

######  Lemma 3.5.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$, let $\varOmega$
be an open semialgebraic subset of $\mathbb{R}^{n}$ disjoint from $W$ and let
$p$ be a positive integer. If $f:\varOmega\longrightarrow\mathbb{R}$ is a
bounded $\Lambda^{0}_{p}(W)$-regular function and
$\varPhi:\mathbb{R}\longrightarrow\mathbb{R}$ is a semialgebraic
$\mathcal{C}^{p}$-function, then $\varPhi\circ f$ is a
$\Lambda^{0}_{p}(W)$-regular function.

###### Proof.

Observe that if $\alpha\in\mathbb{N}^{n}$ and $1\leq|\alpha|\leq p$, then
$D^{\alpha}(\varPhi\circ f)$ can be represented as a linear combination, with
integral coefficients independent of $\varPhi$ and $f$, of products of the
form

$\varPhi^{(i)}(f)(D^{\beta_{1}}f)\dots(D^{\beta_{i}}f),$

where $1\leq i\leq|\alpha|$ and
$\beta_{1},\dots,\beta_{i}\in\mathbb{N}^{n}\setminus\\{0\\}$ are such that
$\beta_{1}+\dots+\beta_{i}=\alpha$. Hence, for some constant $C>0$

$|D^{\alpha}(\varPhi\circ f)(x)|\leq Cd(x,W)^{-|\beta_{1}|}\dots
d(x,W)^{-|\beta_{i}|}=Cd(x,W)^{-|\alpha|}.$

∎

######  Definition 3.6.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let
$Z\subset\mathbb{R}^{n}\setminus W$. We will say that _the property
$\mathcal{B}_{n}(Z,W)$ holds_, if for any positive integer $p$ and for any
$\eta>0$ there exists a $\Lambda^{0}_{p}(W)$-regular function
$\psi:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$ such that

(3.1) $\psi\equiv 1$ on $G_{\rho}(Z,W)$, with some $\rho\in(0,\eta)$, and
(3.2) $\rm supp$$\psi\subset G_{\eta}(Z,W).$

######  Lemma 3.7.

If $W$ is a closed semialgebraic subset of $\mathbb{R}^{n}$,
$Z_{1},Z_{2},Z\subset\mathbb{R}^{n}\setminus W$ and
$\varepsilon,\eta\in(0,+\infty)$, then

$G_{\eta}(Z_{1}\cup Z_{2},W)=G_{\eta}(Z_{1},W)\cup
G_{\eta}(Z_{2},W)\quad\text{and}\quad G_{\varepsilon}(G_{\eta}(Z,W),W)\subset
G_{\varepsilon+\eta+\varepsilon\eta}(Z,W).$

###### Proof.

The first being straightforward, we will check the second inclusion. Let $x\in
G_{\varepsilon}(G_{\eta}(Z,W),W)$. Hence, $d(x,G_{\eta}(Z,W))<\varepsilon
d(x,W)$. It follows that there exists $y\in G_{\eta}(Z,W)$ such that
$|x-y|<\varepsilon d(x,W)$. On the other hand $d(y,Z)<\eta d(y,W)$; thus,

$d(x,Z)\leq|x-y|+d(y,Z)<\varepsilon d(x,W)+\eta d(y,W)\leq\varepsilon
d(x,W)+\eta[|x-y|+d(x,W)]<$ $\varepsilon d(x,W)+\eta\varepsilon d(x,W)+\eta
d(x,W)=(\varepsilon+\eta+\varepsilon\eta)d(x,W).$

∎

######  Lemma 3.8.

If $W$ is a closed semialgebraic subset of $\mathbb{R}^{n}$ and
$Z_{1},\dots,Z_{k}\subset\mathbb{R}^{n}\setminus W$ and if
$\mathcal{B}_{n}(Z_{i},W)$ holds for every $i\in\\{1,\dots,k\\}$, then
$\mathcal{B}_{n}(\bigcup_{i=1}^{k}Z_{i},W)$ holds.

###### Proof.

Take a piecewise polynomial $\mathcal{C}^{p}$-function
$P:\mathbb{R}\longrightarrow[0,1]$ such that $P(t)=1$, when $t\leq 1/3$, and
$P(t)=0$, when $t\geq 2/3$. For any given $\eta>0$, let
$\psi_{i}:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$
$(i\in\\{1,\dots,k\\})$ be a $\Lambda^{0}_{p}(W)$-regular function such that
$\psi_{i}=1$ on $G_{\rho}(Z_{i},W)$, where $\rho\in(0,\eta)$, and $\rm
supp$$\psi_{i}\subset G_{\eta}(Z_{i},W)$. Since, by Lemma 3.7,
$G_{\eta}(\bigcup_{i=1}^{k}Z_{i},W)=\bigcup_{i=1}^{k}G_{\eta}(Z_{i},W)$, the
function

$\psi:\mathbb{R}^{n}\setminus W\ni x\longmapsto
1-P\Big{(}\sum_{i=1}^{k}\psi_{i}(x)\Big{)}\in[0,1]$

is a $\varLambda^{0}_{p}(W)$-regular function (by Lemma 3.5) corresponding to
$\bigcup_{i=1}^{k}Z_{i}$. ∎

######  Proposition 3.9.

For any closed semialgebraic subset $W$ of $\mathbb{R}^{n}$ and any
semialgebraic $Z\subset\mathbb{R}^{n}\setminus W$, the property
$\mathcal{B}_{n}(Z,W)$ holds.

###### Proof.

We argue by induction on $m=\dim Z$. If $m=0$, in view of Lemma 3.8, one can
assume that $Z=\\{z\\}$ is a singleton. If $\eta>0$, then there exists
$\rho\in(0,\eta)$ and $0<r<R$ such that

$\text{$G_{\rho}(\\{z\\},W)\subset B(z,r)\subset B(z,R)\subset
G_{\eta}(\\{z\\},W)$},$

where $B(z,r):=\\{x\in\mathbb{R}^{n}:\,|x-z|\leq r\\}$. Now, it is enough to
take a semialgebraic $\mathcal{C}^{p}$-function
$\psi:\mathbb{R}^{n}\longrightarrow[0,1]$ such that $\psi=0$ on
$\mathbb{R}^{n}\setminus B(z,R)$ and $\psi=1$ on $B(z,r)$.

Let now $m\in\\{1,\dots,n-1\\}$ and assume that
$\mathcal{B}_{n}(Z^{\prime},W)$ holds for any semialgebraic subset
$Z^{\prime}\subset\mathbb{R}^{n}\setminus W$, such that $\dim Z^{\prime}<m$.

By Theorem 2.6 applied to the sets $Z$ and $W$ and to the Lipschitz function
$g(x):=d(x,W)$, combined with Lemma 3.8 and the induction hypothesis, we
reduce the general case to that where $Z$ is a $\Lambda_{p}$-regular cell
(2.3);

$Z=\\{(u,w):\,u\in T,w=\varphi(u)\\},$

where $u=(x_{1},\dots,x_{m})$, $w=(x_{m+1},\dots,x_{n})$, $T$ is an open
$\Lambda_{p}$-regular cell in $\mathbb{R}^{m}$, and
$\varphi:T\longrightarrow\mathbb{R}^{n-m}$ is a semialgebraic
$\Lambda_{p}$-regular mapping, and moreover, the function

$T\ni u\longmapsto d\big{(}(u,\varphi(u)),W\big{)}\in\mathbb{R}$

is $\Lambda_{p}$-regular.

It is elementary that if $M\geq 0$ is a Lipschitz constant of the mapping
$\varphi$, then putting $L:=1/\sqrt{1+M^{2}}$, we have

(3.3) $\forall x=(u,w)\in T\times\mathbb{R}^{n-m}:\,L|w-\varphi(u)|\leq
d(x,Z)\leq|w-\varphi(u)|$

and

(3.4)
$\forall\,x\in\mathbb{R}^{n}\setminus(T\times\mathbb{R}^{n-m}):\,d(x,Z)\geq
Ld(x,\partial Z).$

Take any $\eta$ such that

(3.5) $0<\eta<L.$

Fix any $\eta^{\prime}\in(0,\eta)$. By the induction hypothesis applied to
$Z^{\prime}:=\partial Z\setminus W$, where $\partial Z:=\overline{Z}\setminus
Z$, there exists a $\Lambda^{0}_{p}(W)$-regular function
$\lambda:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$ such that $\rm
supp$$\lambda\subset G_{\eta^{\prime}}(Z^{\prime},W)$ and $\lambda\equiv 1$ on
$G_{\rho^{\prime}}(Z^{\prime},W)$, for some
$\rho^{\prime}\in(0,\eta^{\prime})$.

Put

$\psi(x)=\psi(u,w):=\big{(}1-\lambda(x)\big{)}P\Big{(}\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\Big{)}+\lambda(x),$

where $x=(u,w)\in T\times\mathbb{R}^{n-m}$, $P$ is a function from the proof
of Lemma 3.8 and $\gamma>0$ is a constant to be carefully chosen. We will show
that the function $\psi$ extends by means of $\lambda$ to a
$\Lambda^{0}_{p}(W)$-regular function $\psi:\mathbb{R}^{n}\setminus
W\longrightarrow[0,1]$, provided that $\gamma>0$ is sufficiently small.

Fix any $\delta\in(0,L)$. According to (3.4), the set

$H:=\\{x\in\mathbb{R}^{n}\setminus W:\,d(x,Z)>\delta d(x,\partial Z)\\}\cup
G_{\rho^{\prime}}(Z^{\prime},W)$

is an open neighborhood of the set
$\big{[}\mathbb{R}^{n}\setminus(T\times\mathbb{R}^{n-m})\big{]}\setminus W$ in
the set $\mathbb{R}^{n}\setminus W$.

######  Lemma 3.10.

We claim that if $\gamma>0$ is sufficiently small, then $\psi=\lambda$ on
$(T\times\mathbb{R}^{n-m})\cap H$.

Indeed, let $x\in(T\times\mathbb{R}^{n-m})\cap H$. If $x\in
G_{\rho^{\prime}}(Z^{\prime},W)$, then clearly $\psi(x)=\lambda(x)$, so let us
assume that $x\not\in G_{\rho^{\prime}}(Z^{\prime},W)$; i.e.

(3.6) $d(x,\partial Z\setminus W)\geq{\rho^{\prime}}d(x,W).$

The following two cases are possible: $d(x,\partial Z)=d(x,(\partial
Z)\setminus W)$, or

$d(x,\partial Z)=d(x,(\partial Z)\cap W)$.

In the first case, we have in view of (3.6)

$d\big{(}(u,\varphi(u)),W\big{)}\leq|(u,\varphi(u))-x|+d(x,W)$
$\leq|w-\varphi(u)|+(1/\rho^{\prime})d(x,\partial
Z)\leq|w-\varphi(u)|+\big{(}1/(\rho^{\prime}\delta)\big{)}d(x,Z)$
$\leq|w-\varphi(u)|+\big{(}1/(\rho^{\prime}\delta)\big{)}|w-\varphi(u)|.$

Hence

$\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\geq\frac{(\rho^{\prime}\delta)^{2}}{\gamma(1+\rho^{\prime}\delta)^{2}}>2/3,$

if only

(3.7)
$0<\gamma<\frac{3(\rho^{\prime}\delta)^{2}}{2(1+\rho^{\prime}\delta)^{2}}.$

In the second case, we have

$d\big{(}(u,\varphi(u)),W\big{)}\leq|(u,\varphi(u))-x|+d(x,W)$
$\leq|w-\varphi(u)|+d(x,(\partial Z)\cap W)=|w-\varphi(u)|+d(x,\partial Z)$
$<|w-\varphi(u)|+(1/\delta)d(x,Z)\leq|w-\varphi(u)|+(1/\delta)|w-\varphi(u)|.$

Hence, if $\gamma$ satisfies (3.7), then we have again

$\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\geq\frac{\delta^{2}}{\gamma(1+\delta)^{2}}>\frac{(\rho^{\prime}\delta)^{2}}{\gamma(1+\rho^{\prime}\delta)^{2}}>2/3,$

since $\rho^{\prime}<1$.

It follows that if $\gamma$ satisfies (3.7), then

$P\Big{(}\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\Big{)}=0,$

hence $\psi(x)=\lambda(x)$, which ends the proof of Lemma 3.10.

Now, we will show that, if $\gamma>0$ satisfies (3.7), then $\rm
supp$$\psi\subset G_{\eta}(Z,W)$. Let $x\in\mathbb{R}^{n}\setminus W$ and
$x\not\in G_{\eta^{\prime}}(Z,W)$, so

(3.8) $d(x,Z)\geq\eta^{\prime}d(x,W).$

In the case when $x\in H$, we have $d(x,Z^{\prime})\geq
d(x,Z)\geq\eta^{\prime}d(x,W)$; hence, $\psi(x)=\lambda(x)=0$. In the case
when $x\not\in H$, we have in particular that $x\in T\times\mathbb{R}^{n-m}$.
As before, $d(x,Z^{\prime})\geq d(x,Z)\geq\eta^{\prime}d(x,W)$; hence,
$\lambda(x)=0$. Moreover,

$d\big{(}(u,\varphi(u)),W\big{)}\leq|(u,\varphi(u))-x|+d(x,W)$
$\leq|w-\varphi(u)|+(1/\eta^{\prime})d(x,Z)\leq|w-\varphi(u)|\frac{\eta^{\prime}+1}{\eta^{\prime}};$

hence, if $\gamma$ satisfies (3.7),

$\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\geq\frac{(\eta^{\prime})^{2}}{\gamma(1+\eta^{\prime})^{2}}>\frac{(\rho^{\prime}\delta)^{2}}{\gamma(1+\rho^{\prime}\delta)^{2})}>2/3,$

consequently

$P\Big{(}\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\Big{)}=0,\quad\text{thus \,
$\psi(x)=\lambda(x)=0$}.$

It follows that $\rm supp$$\psi\subset G_{\eta}(Z,W)$.

Now we will find $\rho\in(0,\eta)$ such that $\psi\equiv 1$ on
$G_{\rho}(Z,W)$. Assume first that

(3.9) $0<\rho<\rho^{\prime}\delta$

and take any $x\in G_{\rho}(Z,W)$; i.e. $d(x,Z)<\rho d(x,W)$.

If $x\in G_{\rho^{\prime}}(Z^{\prime},W)$, then $\psi(x)=\lambda(x)=1$, so in
what follows we can assume that $x\not\in G_{\rho^{\prime}}(Z^{\prime},W)$;
i.e.

(3.10) $d(x,Z^{\prime})\geq\rho^{\prime}d(x,W).$

Consider two possible cases exactly as in the proof of Lemma 3.10. If
$d(x,\partial Z)=d(x,Z^{\prime})$, then by (3.9) and (3.10)

$d(x,Z)<\rho d(x,W)<\rho^{\prime}\delta d(x,W)\leq\delta
d(x,Z^{\prime})=\delta d(x,\partial Z),$

which implies that $x\not\in H$. If $d(x,\partial Z)=d(x,(\partial Z)\cap W)$,
then

$d(x,Z)<\rho d(x,W)<\rho^{\prime}\delta d(x,W)<\delta d(x,W)\leq\delta
d(x,(\partial Z)\cap W)=\delta d(x,\partial Z),$

which again implies that $x\not\in H$.

Consider now $x\in G_{\rho}(Z,W)\setminus H$. Then in particular $x=(u,w)\in
T\times\mathbb{R}^{n-m}$ and, according to (3.3),

$L|w-\varphi(u)|\leq d(x,Z)<\rho d(x,W)\leq\rho|x-(u,\varphi(u))|+\rho
d\big{(}(u,\varphi(u)),W\big{)}$ $=\rho|w-\varphi(u)|+\rho
d\big{(}(u,\varphi(u)),W\big{)}.$

Hence, if we assume that

(3.11) $0<\rho<L\frac{\sqrt{\gamma}}{\sqrt{3}+\sqrt{\gamma}},$

then

$\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\leq\frac{\rho^{2}}{\gamma(L-\rho)^{2}}<1/3;$

consequently,

$P\Big{(}\frac{|w-\varphi(u)|^{2}}{\gamma
d\big{(}(u,\varphi(u)),W\big{)}^{2}}\Big{)}=1,\quad\text{thus \,\,
$\psi(x)=1$}.$

We conclude that $\psi\equiv 1$ on $G_{\rho}(Z,W)$, if only $\rho$ satisfies
(3.9) and (3.11).

Now we will check that $\psi:\mathbb{R}^{n}\longrightarrow[0,1]$ is
$\Lambda^{0}_{p}(W)$ regular. Since $\psi=\lambda$ on $H$ and $\lambda$ is
$\Lambda^{0}_{p}(W)$-regular, due to induction hypothesis, it suffices to
check $\Lambda^{0}_{p}(W)$-regularity on
$\mathbb{R}^{n}\setminus(\overline{H}\cup W)$. Moreover, since $\rm
supp$$\psi\subset G_{\eta}(Z,W)$ and $\psi\equiv 1$ on $G_{\rho}(Z,W)$, it
suffices to check $\Lambda^{0}_{p}(W)$-regularity, assuming that

(3.12) $x\in\mathbb{R}^{n}\setminus(\overline{H}\cup W),\,d(x,Z)<\eta d(x,W),$

$\phantom{.......................................}\text{and}\,\,d(x,Z^{\prime})>\rho^{\prime}d(x,W).$

For $x=(u,w)\in T\times\mathbb{R}^{n-m}$ satisfying (3.12), we have by (3.3)
and (3.5) that

$d(x,W)\leq d\big{(}(u,\varphi(u)),W\big{)}+|x-(u,\varphi(u))|$ $\leq
d\big{(}(u,\varphi(u)),W\big{)}+(1/L)d(x,Z)<d\big{(}(u,\varphi(u)),W\big{)}+(\eta/L)d(x,W);$

consequently,

(3.13) $d(x,W)<\frac{L}{L-\eta}d\big{(}(u,\varphi(u)),W).$

Since by (3.3), (3.12) and (3.13)

$\frac{|w-\varphi(u)|}{d\big{(}(u,\varphi(u)),W\big{)}}\leq\frac{(1/L)d(x,Z)}{\big{(}1-(\eta/L)\big{)}d(x,W)}<\frac{\eta}{L-\eta},$

and

$\frac{|w-\varphi(u)|^{2}}{d\big{(}(u,\varphi(u)),W\big{)}^{2}}=\sum_{j=m+1}^{n}\Big{[}\frac{x_{j}-\varphi_{j}(u)}{d\big{(}(u,\varphi(u)),W\big{)}}\Big{]}^{2},$

where $\varphi=(\varphi_{m+1},\dots,\varphi_{n})$, it follows from Lemmas 3.4,
3.3 and 3.5 consecutively applied, that it suffices to check that every
function $f_{j}(x)=f_{j}(u,w):=\varphi_{j}(u)$ and the function
$g(x)=g(u,w):=d\big{(}(u,\varphi(u)),W\big{)}$ are
$\Lambda^{1}_{p}(W)$-regular222$x_{j}$ was omitted as obviously
$\Lambda^{1}_{p}(W)$-regular on the set (3.12).

To this end, take any $\alpha\in\mathbb{N}^{n}\setminus\\{0\\}$ such that
$|\alpha|\leq p$. Then for any $x=(u,w)$ satisfying (3.12),

$|D^{\alpha}f_{j}(x)|\leq Cd(u,\partial T)^{1-|\alpha|}\leq
CL^{1-|\alpha|}d\big{(}(u,\varphi(u)),\partial Z)^{1-|\alpha|}$ $\leq
CL^{1-|\alpha|}\max\Big{[}d\big{(}(u,\varphi(u)),Z^{\prime}\big{)}^{1-|\alpha|},d\big{(}(u,\varphi(u)),(\partial
Z)\cap W\big{)}^{1-|\alpha|}\Big{]},$

where $C$ is a positive constant.

On the other hand, by (3.3) and (3.12),

$d\big{(}(u,\varphi(u)),Z^{\prime}\big{)}\geq
d(x,Z^{\prime})-|w-\varphi(u)|\geq d(x,Z^{\prime})-(1/L)d(x,Z)$ $\geq
d(x,Z^{\prime})-(\delta/L)d(x,\partial Z)\geq
d(x,Z^{\prime})-(\delta/L)d(x,Z^{\prime})\geq\rho^{\prime}\Big{(}1-\frac{\delta}{L}\Big{)}d(x,W),$

and, by (3.13),

$d\big{(}(u,\varphi(u)),(\partial Z)\cap W\big{)}\geq
d\big{(}(u,\varphi(u)),W\big{)}>\Big{(}1-\frac{\eta}{L}\Big{)}d(x,W).$

It follows that $|D^{\alpha}f_{j}(x)|\leq\tilde{C}d(x,W)^{1-|\alpha|}$, where
$\tilde{C}$ is a positive constant. The same estimate holds for $g$, which
ends the proof that $\psi$ is $\Lambda^{0}_{p}(W)$-regular.

To finish the proof of Proposition 3.9, it remains to consider the case $m=n$;
i.e. $Z$ is an open semialgebraic subset of $\mathbb{R}^{n}\setminus W$. Let
$\eta>0$. By induction hypothesis applied to $Z^{\prime}:=\partial Z\setminus
W$, there exists a $\Lambda^{0}_{p}(W)$-regular function
$\lambda:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$ such that $\rm
supp$$\lambda\subset G_{\eta}(Z^{\prime},W)$ and $\lambda\equiv 1$ on
$G_{\rho}(Z^{\prime},W)$, for some $\rho\in(0,\eta)$. Now, we define

$\psi(x):=\begin{cases}1,&\text{when $x\in Z$}\\\ \lambda(x),&\text{when
$x\in\big{[}(\mathbb{R}^{n}\setminus W)\setminus\overline{Z}\big{]}\cup
G_{\rho}(Z^{\prime},W)$.}\end{cases}$

Clearly, $\psi:\mathbb{R}^{n}\setminus W\longrightarrow[0,1]$ is
$\Lambda^{0}_{p}(W)$-regular, $\rm supp$$\psi\subset G_{\eta}(Z,W)$ and
$\psi\equiv 1$ on $G_{\rho}(Z,W)$. ∎

###### Proof of Theorem 3.2.

By Proposition 3.9, for each $i\in\\{1,\dots,s\\}$, there exists a
$\Lambda^{0}_{p}(W)$-regular function $\psi_{i}:\mathbb{R}^{n}\setminus
W\longrightarrow[0,1]$ such that $\rm supp$$\psi_{i}\subset G_{\eta}(U_{i},Z)$
and $\psi_{i}\equiv 1$ on $G_{\rho_{i}}(U_{i},W)$, for some
$\rho_{i}\in(0,\eta)$. By Lemmas 3.4 and 3.3, the functions

$\omega_{i}:=\frac{\psi_{i}}{\psi_{1}+\dots+\psi_{s}}\quad(i\in\\{1,\dots,s\\}).$

are the required partition of unity. ∎

##  4\. Proof of Theorem 1.3

By Theorem 2.6, applied to $g$ and the set $W$, we obtain a
$\Lambda_{p}$-regular stratification $\mathbb{R}^{n}\setminus
W=C_{1}\cup\dots\cup C_{s}$ of the set $\mathbb{R}^{n}\setminus W$, such that,
for each $i\in\\{1,\dots,s\\}$, the stratum $C_{i}$, after an orthogonal
linear change of coordinates in $\mathbb{R}^{n}$, is a $\Lambda_{p}$-regular
cell in $\mathbb{R}^{n}$ and if $C_{i}$ is open then $g|C_{i}$ is
$\Lambda_{p}$-regular, while in the case $\dim C_{i}=m<n$, when $C_{i}$ is of
the form

(4.1) $C_{i}=\\{(u,w)\in D_{i}\times\mathbb{R}^{n-m}:w=\varphi_{i}(u)\\},$

where $D_{i}$ is open in $\mathbb{R}^{m}$ and
$\varphi_{i}:D_{i}\longrightarrow\mathbb{R}^{n-m}$ is $\Lambda_{p}$-regular,
then

(4.2) the mapping $D_{i}\ni u\longmapsto g(u,\varphi_{i}(u))\in\mathbb{R}^{d}$
is $\Lambda_{p}$-regular.

Additionally, without any loss in generality, we can assume that

(4.3) $\dim C_{1}\leq\dim C_{2}\leq\dots\leq\dim C_{s}.$

If $C_{i}$ is of the form (4.1) and $M_{i}$ is a Lipschitz constant of
$\varphi_{i}$, then we put $L_{i}:=1/\sqrt{1+M_{i}^{2}}$. If $\dim C_{i}=n$,
we put $L_{i}:=1$. Let $A$ be a Lipschitz constant of $g$.

To simplify the notation, we will write in this section $G_{\eta}(Z)$ in the
place of $G_{\eta}(Z,W)$, for any $\eta>0$ and any semialgebraic subset
$Z\subset\mathbb{R}^{n}\setminus W$. This will not lead to a confusion because
the set $W$ is fixed in this section.

Given any $\kappa>0$ as in Theorem 1.3, fix any $\theta\in(0,1)$ so small that
$A(\theta/L_{i})<\kappa$, for each $i\in\\{1,\dots,s\\}$. We define by
induction on $i\in\\{1,\dots,s\\}$, a sequence of semialgebraic sets
$Z_{1}\subset C_{1},\dots,Z_{s}\subset C_{s}$, and two sequences of positive
numbers
$\eta_{s}<\delta_{s}<\eta_{s-1}<\delta_{s-1}<\dots<\eta_{1}<\delta_{1}<\theta$
such that

(4.4) $d(x,C_{1}\cup\dots\cup
C_{i})<\eta_{i}d(x,W)\Longrightarrow\phantom{..........................................}$

$\phantom{.............................}x\in G_{\eta_{i}}(Z_{i})\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(Z_{i-1}))\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots));$

(4.5) there exists a $\Lambda^{1}_{p}(W)$-regular function
$f_{i}:G_{\delta_{i}}(Z_{i})\longrightarrow\mathbb{R}\phantom{.........}$

$\phantom{.....................}\text{such that}\quad\forall\,x\in
G_{\delta_{i}}(Z_{i}):\,|f_{i}(x)-g(x)|\leq A(\delta_{i}/L_{i})d(x,W)$;

(4.6) for every $j\in\\{1,\dots,i\\}$ there exists
$\varepsilon_{ij}\in(0,\delta_{j})$ such that

$\phantom{.....................}G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{j}}(Z_{j}))\dots))\subset
G_{\varepsilon_{ij}}(Z_{j}).$

To begin the inductive definition, we put $Z_{1}:=C_{1}$. Since $C_{1}$ is the
first stratum, its boundary $\partial Z_{1}:=\overline{Z_{1}}\setminus Z_{1}$
is contained in $W$. Take any $\delta_{1}<\min\\{\theta,L_{1}\\}$. Then, for
each $x\in G_{\delta_{1}}(Z_{1})$, we have

$d(x,Z_{1})<\delta_{1}d(x,W)\leq\delta_{1}d(x,\partial Z_{1});$

hence, by (3.4), $x=(u,w)\in D_{1}\times\mathbb{R}^{n-m_{1}}$, where
$m_{1}=\dim C_{1}$. Therefore, we can define

$f_{1}(x)=f_{1}(u,w):=g(u,\varphi_{1}(u)).$

Then, by (3.3),

$|f_{1}(x)-g(x)|=|g(u,\varphi_{1}(u))-g(u,w)|\leq A|w-\varphi_{1}(u)|$ $\leq
AL_{1}^{-1}d(x,C_{1})\leq A(\delta_{1}/L_{1})d(x,W).$

To check that $f_{1}$ is $\Lambda^{1}_{p}(W)$-regular, we take any
$\alpha\in\mathbb{N}^{n}\setminus\\{0\\}$ such that $|\alpha|\leq p$. Then we
have by (4.2)

$|D^{\alpha}f_{1}(x)|\leq B_{1}d(u,\partial D_{1})^{1-|\alpha|}\leq
B_{1}(L_{1})^{1-|\alpha|}d\big{(}(u,\varphi_{1}(u)),\partial
Z_{1}\big{)}^{1-|\alpha|}$ $\leq B_{1}(L_{1})^{1-|\alpha|}\Big{[}d(x,\partial
Z_{1})-|w-\varphi_{1}(u)|\Big{]}^{1-|\alpha|}$ $\leq
B_{1}(L_{1})^{1-|\alpha|}\Big{[}d(x,\partial
Z_{1})-L_{1}^{-1}d(x,Z_{1})\Big{]}^{1-|\alpha|}$ $\leq
B_{1}(L_{1})^{1-|\alpha|}\Big{(}1-\frac{\delta_{1}}{L_{1}}\Big{)}^{1-|\alpha|}d(x,W)^{1-|\alpha|},$

where $B_{1}$ is a positive constant. Fix any $\eta_{1}\in(0,\delta_{1})$ and
put $\varepsilon_{11}:=\eta_{1}$.

To define $Z_{i+1}$, where $i<s$, observe that, due to (4.3) and (4.4),

$(\partial C_{i+1})\setminus W\subset C_{1}\cup\dots\cup C_{i}\subset
G_{\eta_{i}}(Z_{i})\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))$

. Put

$Z_{i+1}:=C_{i+1}\setminus\Big{[}G_{\eta_{i}}(Z_{i})\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))\Big{]}.$

By (4.4)

(4.7) $\forall\,z\in Z_{i+1}:\,\,d(z,\partial
C_{i+1})=\min\big{\\{}d(z,(\partial C_{i+1})\setminus W),d(z,(\partial
C_{i+1})\cap W)\big{\\}}\geq$
$\phantom{....}\min\big{\\{}d(z,C_{1}\cup\dots\cup
C_{i}),d(z,W)\big{\\}}\geq\eta_{i}d(z,W).$

Assume first that $\dim C_{i+1}<n$. Then we choose
$\delta_{i+1}\in(0,\eta_{i}/(1+\eta_{i}))$ in such a way that

(4.8) $\frac{\delta_{i+1}}{\eta_{i}-\delta_{i+1}(\eta_{i}+1)}<L_{i+1}.$

We will now check that

(4.9) $G_{\delta_{i+1}}(Z_{i+1})\subset D_{i+1}\times\mathbb{R}^{n-m_{i+1}}.$

Indeed, take any $x\in G_{\delta_{i+1}}(Z_{i+1})$. There exists $z\in Z_{i+1}$
such that $|x-z|<\delta_{i+1}d(x,W)$. By (4.7), we have

$|x-z|<\delta_{i+1}\big{(}|x-z|+d(z,W)\big{)}\leq\leq\delta_{i+1}|x-z|+\frac{\delta_{i+1}}{\eta_{i}}d(z,\partial
C_{i+1})\leq$
$\big{(}\delta_{i+1}+\frac{\delta_{i+1}}{\eta_{i}}\big{)}|x-z|+\frac{\delta_{i+1}}{\eta_{i}}d(x,\partial
C_{i+1})$

hence,

$d(x,C_{i+1})\leq|x-z|<\frac{\delta_{i+1}}{\eta_{i}-\delta_{i+1}(\eta_{i}+1)}d(x,\partial
C_{i+1})$

which, in view of (4.8) and (3.4), implies that $x\in
D_{i+1}\times\mathbb{R}^{n-m_{i+1}}$.

In view of (4.9), the following definition of
$f_{i+1}:G_{\delta_{i+1}}(Z_{i+1})\longrightarrow\mathbb{R}$ is possible

$f_{i+1}(x)=f_{i+1}(u,w):=g(u,\varphi_{i+1}(u)).$

Then, we have

$|f_{i+1}(x)-g(x)|\leq A|w-\varphi_{i+1}(u)|\leq(A/L_{i+1})d(x,C_{i+1})$
$\leq(A/L_{i+1})d(x,Z_{i+1})<A(\delta_{i+1}/L_{i+1})d(x,W).$

Now we want to check that $f_{i+1}$ is $\Lambda^{1}_{p}(W)$-regular. Let
$\alpha\in\mathbb{N}^{n}\setminus\\{0\\}$ such that $|\alpha|\leq p$ and let
$x\in G_{\delta_{i+1}}(Z_{i+1})$. Then there exists $z\in Z_{i+1}$ such that
$|x-z|<\delta_{i+1}d(x,W)$. By (4.2) and (4.7), we get

$|D^{\alpha}f_{i+1}(x)|\leq B_{i+1}d(u,\partial D_{i+1})^{1-|\alpha|}$ $\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}d\big{(}(u,\varphi_{i+1}(u)),\partial
C_{i+1}\big{)}^{1-|\alpha|}$ $\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}d(z,\partial
C_{i+1})-|(u,\varphi_{i+1}(u))-z|\Big{]}^{1-|\alpha|}$ $\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(z,W)-|(u,\varphi_{i+1}(u))-z|\Big{]}^{1-|\alpha|}$
$\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(x,W)-\eta_{i}|x-z|-|x-z|-|(u,\varphi_{i+1}(u))-x|\Big{]}^{1-|\alpha|}$
$\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(x,W)-(\eta_{i}+1)|x-z|-|w-\varphi_{i+1}(u)|\Big{]}^{1-|\alpha|}$
$\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(x,W)-(\eta_{i}+1)\delta_{i+1}d(x,W)-(1/L_{i+1})d(x,C_{i+1})\Big{]}^{1-|\alpha|}$
$\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(x,W)-(\eta_{i}+1)\delta_{i+1}d(x,W)-(1/L_{i+1})d(x,Z_{i+1})\Big{]}^{1-|\alpha|}$
$\leq
B_{i+1}(L_{i+1})^{1-|\alpha|}\Big{[}\eta_{i}d(x,W)-(\eta_{i}+1)\delta_{i+1}d(x,W)-(\delta_{i+1}/L_{i+1})d(x,W)\Big{]}^{1-|\alpha|}$
$=B_{i+1}[\eta_{i}-\delta_{i+1}(\eta_{i}+1)]^{1-|\alpha|}\Big{(}L_{i+1}-\frac{\delta_{i+1}}{\eta_{i}-\delta_{i+1}(\eta_{i}+1)}\Big{)}^{1-|\alpha|}d(x,W)^{1-|\alpha|},$

where $B_{i+1}$ is a positive constant.

Assume now that $\dim C_{i+1}=n$. Then we fix any
$\delta_{i+1}\in(0,\eta_{i}/(1+\eta_{i}))$. If $x\in
G_{\delta_{i+1}}(Z_{i+1})$, then there exists $z\in Z_{i+1}$ such that
$|x-z|<\delta_{i+1}d(x,W)$, and by (4.7)

$|x-z|<\delta_{i+1}|x-z|+\delta_{i+1}d(z,W)\leq\delta_{i+1}|x-z|+\frac{\delta_{i+1}}{\eta_{i}}d(z,\partial
C_{i+1});$

thus,

$|x-z|<\frac{\delta_{i+1}}{(1-\delta_{i+1})\eta_{i}}d(z,\partial
C_{i+1})<d(z,\partial C_{i+1}).$

It follows that

(4.10) $G_{\delta_{i+1}}(Z_{i+1})\subset C_{i+1};$

hence we can define $f_{i+1}$ as the restriction $g|C_{i+1}$ of $g$ to
$C_{i+1}$. Clearly, $f_{i+1}$ is $\varLambda_{p}^{1}(W)$-regular and
corresponding condition (4.5) is trivially satisfied, since then the left-hand
side is identically zero.

Now we will need to specify $\eta_{i+1}\in(0,\delta_{i+1})$. To this end we
will need the properties of the operation $G_{\delta}$ expressed in Lemma 3.7.
We take any $\eta_{i+1}\in(0,\delta_{i+1})$ so small that

$\varepsilon_{i+1,j}:=\varepsilon_{ij}+\eta_{i+1}+\eta_{i+1}\varepsilon_{ij}<\delta_{j}\qquad(j\in\\{1,\dots,i\\})$

and $\varepsilon_{i+1,i+1}:=\eta_{i+1}$, both in the case $\dim C_{i+1}<n$ as
well as when $\dim C_{i+1}=n$. This choice ensures (4.6) for $i+1$ in the
place of $i$, according to Lemma 3.7.

Now we will check the property (4.4) for $i+1$ in the place of $i$.

Let $d(x,C_{1}\cup\dots\cup C_{i}\cup C_{i+1})<\eta_{i+1}d(x,W)$.

If $d(x,C_{1}\cup\dots\cup C_{i}\cup C_{i+1})=d(x,C_{1}\cup\dots\cup C_{i})$,
then by (4.4), $x\in G_{\eta_{i}}(Z_{i})\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(Z_{i-1}))\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))$.

If $d(x,C_{1}\cup\dots\cup C_{i}\cup C_{i+1})=d(x,Z_{i+1})$, then certainly
$d(x,Z_{i+1})<\eta_{i+1}d(x,W)$; thus, $x\in G_{\eta_{i+1}}(Z_{i+1})$.

It remains the case, when $d(x,C_{1}\cup\dots\cup C_{i}\cup C_{i+1})=$

$d\Big{(}x,C_{i+1}\cap\big{[}G_{\eta_{i}}(Z_{i})\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(Z_{i-1}))\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))\big{]}\Big{)}.$

Then

$d\Big{(}x,G_{\eta_{i}}(Z_{i})\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(Z_{i-1}))\cup\dots\cup
G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))\Big{)}$

$\phantom{.........................................................................................}<\eta_{i+1}d(x,W)$;
thus,

$x\in G_{\eta_{i+1}}(G_{\eta_{i}}(Z_{i}))\cup
G_{\eta_{i+1}}(G_{\eta_{i}}(G_{\eta_{i-1}}(Z_{i-1})))\cup\dots\phantom{.........................}$
$\phantom{..........................................}\dots\cup
G_{\eta_{i+1}}(G_{\eta_{i}}(G_{\eta_{i-1}}(\dots(G_{\eta_{1}}(Z_{1}))\dots))).$

To finish the proof of Theorem 1.3, we put

$U_{i}:=G_{\eta_{s}}(\dots(G_{\eta_{i}}(Z_{i}))\dots),\quad\text{for
$i\in\\{1,\dots,s\\}$},$

and choose $\eta>0$ so small that $G_{\eta}(U_{i})\subset
G_{\delta_{i}}(Z_{i})$, for each $i\in\\{1,\dots,s\\}$ (see (4.6) and Lemma
3.7). It follows from (4.4) that $U_{1},\dots,U_{s}$ is a covering of
$\mathbb{R}^{n}\setminus W$. We take now the partition of unity
$\\{\omega_{i}\\}$ $(i\in\\{1,\dots,s\\})$ adapted to this covering and to
$\eta$ according to Theorem 3.2. In virtue of Lemma 3.3, for each
$i\in\\{1,\dots,s\\}$, the function $f_{i}\omega_{i}$ is
$\varLambda_{p}^{1}(W)$-regular on $G_{\delta_{i}}(Z_{i})$ and obviously
extends by zero to a $\varLambda_{p}^{1}(W)$-regular function defined on
$\mathbb{R}^{n}\setminus W$ and, by (4.5), for each
$x\in\mathbb{R}^{n}\setminus W$,

$|f_{i}(x)\omega_{i}(x)-g(x)\omega_{i}(x)|\leq
A(\delta_{i}/L_{i})d(x,W)\omega_{i}(x)\leq
A(\theta/L_{i})d(x,W)\omega_{i}(x)<\kappa d(x,W)\omega_{i}(x).$

Hence the function

$f:=f_{1}\omega_{1}+\dots+f_{s}\omega_{s},$

is $\varLambda_{p}^{1}(W)$-regular on $\mathbb{R}^{n}\setminus W$ and for each
$x\in\mathbb{R}^{n}\setminus W$

$|f(x)-g(x)|\leq\sum_{i=1}^{s}|f_{i}(x)\omega_{i}(x)-g(x)\omega_{i}(x)|\leq\sum_{i=1}^{s}\kappa
d(x,W)\omega_{i}(x)=\kappa d(x,W),$

which ends the proof of Theorem 1.3.

##  5\. Two applications

We give here two almost immediate consequences of Theorem 1.1. The first one
is another proof of a theorem of Bierstone, Milman and Pawłucki (cf. [3,
C.11]) that, given any positive integer $p$, any closed semialgebraic (or,
more generally, definable in some o-minimal structure $\mathcal{S}$) subset
$W$ of $\mathbb{R}^{n}$ is the zero-set of some semialgebraic (respectively,
definable in $\mathcal{S}$) $\mathcal{C}^{p}$-function defined on
$\mathbb{R}^{n}$. We will prove the following.

######  Theorem 5.1.

Let $W$ be a closed semialgebraic subset of $\mathbb{R}^{n}$ and let $p$ be a
positive integer. Then there exists a semialgebraic function
$h:\mathbb{R}^{n}\longrightarrow[0,\infty)$ of class $\mathcal{C}^{p}$, which
is Nash on $\mathbb{R}^{n}\setminus W$ and such that $W=h^{-1}(0)$. Moreover,
$h$ is equivalent to the $(p+1)$-th power of the distance function from the
set $W$.

In the proof we will use the following elementary Hestenes Lemma (cf. [15,
Lemme 4.3]).

######  Lemma 5.2.

Let $W$ be a closed subset of an open subset $\varOmega$ of $\mathbb{R}^{n}$.
If $h:\varOmega\setminus W\longrightarrow\mathbb{R}$ is a
$\mathcal{C}^{p}$-function and

$\lim_{x\to a}D^{\alpha}h(x)=0,$

for each $a\in W\cap\overline{\varOmega\setminus W}$ and each
$\alpha\in\mathbb{N}^{n}$ such that $|\alpha|\leq p$, then $h$ extends by zero
to a $\mathcal{C}^{p}$-function on $\varOmega$, $p$-flat on $W$.

###### Proof of Theorem 5.1.

By Theorem 1.1 there exists a semialgebraic $\Lambda^{1}_{p}(W)$-regular Nash
function $f:\mathbb{R}^{n}\setminus W\longrightarrow(0,\infty)$ equivalent to
the function $\mathbb{R}^{n}\setminus W\ni x\longmapsto d(x,W)$. When we put
$h:=f^{p+1}$, we have, for any $\alpha\in\mathbb{N}^{n}$ such that
$|\alpha|\leq p$ and any $x\in\varOmega\setminus W$

(5.1)
$D^{\alpha}h(x)=\sum_{\beta_{1}+\dots+\beta_{p+1}=\alpha}\frac{\alpha!}{\beta_{1}!\dots\beta_{p+1}!}D^{\beta_{1}}f(x)\dots
D^{\beta_{p+1}}f(x).$

It follows that

$|D^{\alpha}h(x)|\leq\sum_{\beta_{1}+\dots+\beta_{p+1}=\alpha}C\big{(}d(x,W)\big{)}^{1-|\beta_{1}|}\dots\big{(}d(x,W)\big{)}^{1-|\beta_{p+1}|}$
$\leq\tilde{C}\big{(}d(x,W)\big{)}^{p+1-|\alpha|},\quad\text{where $C$ and
$\tilde{C}$ are positive constants,}$

which implies that $\lim_{x\to a}D^{\alpha}h(x)=0$, for each $a\in
W\cap\overline{\mathbb{R}^{n}\setminus W}$. ∎

Our second application concerns approximation of semialgebraic subsets by Nash
compact hypersurfaces in the Hausdorff metric. To formulate the result let us
denote by $\mathcal{K}_{n}$ the set of all nonempty compact subsets of
$\mathbb{R}^{n}$. Recall that the _Hausdorff metric_ on $\mathcal{K}_{n}$ is
defined by the formula

$d_{\mathcal{H}}(A,B):=\max\\{\sup_{x\in A}d(x,B),\sup_{y\in B}d(y,A)\\}.$

######  Theorem 5.3.

Let $W$ be a non-empty, compact, nowhere dense semialgebraic subset of
$\mathbb{R}^{n}$. Then there exists a semialgebraic family of Nash compact
hypersurfaces $\\{H_{t}\\}$ $(0<t<\theta)$ such that

$\lim_{t\to 0}d_{\mathcal{H}}(H_{t},W)=0.$

###### Proof.

Let $f:\mathbb{R}^{n}\setminus W\longrightarrow(0,\infty)$ be a Nash function
such that for some positive constant $A$

(5.2) $\forall\,x\in\mathbb{R}^{n}\setminus W:\,\,A^{-1}d(x,W)\leq f(x)\leq
Ad(x,W).$

By Sard’s theorem, the function $f$ has only finitely many critical values;
hence, the set $H_{t}:=f^{-1}(t)$ is a Nash hypersurface in $\mathbb{R}^{n}$,
for all $t>0$ sufficiently small. We will show that $H_{t}$ are compact and
their Hausdorff limit is $W$, when $t$ tends to $0$. For any subset $X$ of
$\mathbb{R}^{n}$ and any $\eta>0$ put

$X^{\eta}:=\\{x\in\mathbb{R}^{n}:\,d(x,X)<\eta\\}.$

To this end, it is enough to show that, for any positive $\eta$ there exists
$\delta>0$ such that for each $t\in(0,\delta)$

(5.3) $H_{t}\subset W^{\eta}\qquad\text{and}\qquad W\subset H_{t}^{\eta}.$

As for the first inclusion (5.3), let $x\in H_{t}$. Then by (5.2),
$A^{-1}d(x,W)\leq t$; hence, if $t<A^{-1}\eta$, then $x\in W^{\eta}$.

As for the second inclusion (5.3), let us define function

(5.4) $\lambda(\varepsilon):=\sup_{a\in W}d(a,\partial
W^{\varepsilon}),\quad\text{for any $\varepsilon>0$.}$

We claim that

(5.5) $\lim_{\varepsilon\to 0}\lambda(\varepsilon)=0.$

Otherwise, by the Curve Selection Lemma, there should exist a semialgebraic
continuous arc $\gamma:(0,\xi)\longrightarrow W$, where $\xi>0$, such that

$\lim_{\varepsilon\to 0}\gamma(\varepsilon)=a,\,\text{for some $a\in W$, and}$
$d(\gamma(\varepsilon),\partial W^{\varepsilon})>\mu,\,\text{for some $\mu>0$
and each $\varepsilon\in(0,\xi)$.}$

The last would mean that

$B(\gamma(\varepsilon),\mu)\subset\\{x\in\mathbb{R}^{n}:\,d(x,W)\leq\varepsilon\\},\,\text{for
each $\varepsilon\in(0,\xi)$.}$

But $B(\gamma(\varepsilon),\mu)\rightarrow B(a,\mu)$ and
$\\{x\in\mathbb{R}^{n}:\,d(x,W)\leq\varepsilon\\}\rightarrow W$, as
$\varepsilon\rightarrow 0$; hence, $B(a,\mu)\subset W$, a contradiction with
our assumption that $W$ is nowhere dense.

Let $\eta>0$. By (5.5), there exists $\delta>0$ such that
$\lambda(\delta)<\eta$. It follows that then

$d(a,\partial W^{\delta})<\eta,\quad\text{for each $a\in W$}.$

Fix any $a\in W$. There exists $z\in\partial W^{\delta}$ such that
$|a-z|=d(a,\partial W^{\delta})$. Observe that the line segment $[a,z]$ has
its endpoints respectively in $W$ and in $\partial W^{\delta}$. By (5.2),

$f^{-1}[0,\delta/A)\subset W^{\delta};$

hence, there exists $y\in f^{-1}(\delta/A)\cap[a,z]$. Then
$|a-y|\leq|a-z|<\eta$ and $y\in H^{\eta}_{\delta/A}$, which shows that
$W\subset H^{\eta}_{\delta/A}$. ∎

Theorem 5.3 is deepened and generalized in our separate article [6].

##  6\. Final remarks

Most of the results of our article remain true in a more general context of
o-minimal structures expanding the field of real numbers $\mathbb{R}$ with the
same proofs, where the term _semialgebraic_ should be replaced by _definable_
and _a Nash mapping_ \- by _a definable $\mathcal{C}^{\infty}$ mapping_.

As for Theorem 1.1, however, it relies heavily on the Efroymson-Shiota
approximation theorem. Theorem 1.4 was generalized by A. Fischer [5, Theorem
1.1]) to o-minimal structures admitting $\mathcal{C}^{\infty}$-cell
decompositions in which the exponential function is definable (the case of
non-polynomially bounded structures). For the case of general polynomially
bounded o-minimal structures admitting $\mathcal{C}^{\infty}$-cell
decompositions a big progress has been made recently by the last author and
Guillaume Valette, who proved that in such structures the Efroymson-Shiota
approximation theorem holds true for $p\leq 1$ ([16, Theorem 4.8]). In
particular, this result allows us to prove the following generalization of
Theorem 5.1.

######  Theorem 6.1.

Let $\mathcal{D}$ be a polynomially bounded o-minimal structure expanding
$\mathbb{R}$ which admits $\mathcal{C}^{\infty}$-cell decompositions. Then,
for any closed $\mathcal{D}$-definable subset $W$ of $\mathbb{R}^{n}$ and any
positive integer $p$, there exists a $\mathcal{D}$-definable
$\mathcal{C}^{p}$-function $h:\mathbb{R}^{n}\longrightarrow[0,\infty)$ which
is $\mathcal{C}^{\infty}$ on $\mathbb{R}^{n}\setminus W$ and such that
$W=h^{-1}(0)$.

###### Proof.

By [16, Theorem 1.1], there exists a $\mathcal{D}$-definable
$\mathcal{C}^{\infty}$-function $f:\mathbb{R}^{n}\setminus
W\longrightarrow[0,\infty)$ such that

$\forall\,x\in\mathbb{R}^{n}\setminus W:A^{-1}f(x)\leq d(x,W)\leq Af(x),$

where $A$ is a positive constant. If $N$ is an integer greater than $p$, then
for any $\alpha\in\mathbb{N}^{n}\setminus\\{0\\}$ such that $|\alpha|\leq p$
the derivative $D^{\alpha}(f^{N})$ is a linear combination with integral
coefficients independent of $f$ of products

$f^{N-k}(D^{\beta_{1}}f)\dots(D^{\beta_{k}}f),$

where $k\in\\{1,\dots,p\\}$,
$\beta_{1},\dots,\beta_{k}\in\mathbb{N}^{n}\setminus\\{0\\}$ and
$\beta_{1}+\dots+\beta_{k}=\alpha$. It follows from the Łojasiewicz inequality
and the Hestenes lemma that for $N$ sufficiently big the function

$h(x):=\begin{cases}f^{N}(x),&\text{when $x\in\mathbb{R}^{n}\setminus W$}\\\
0,&\text{when $x\in W$}\end{cases}$

is the required function. ∎

## References

  * [1]
  * [2] J. Bochnak, M. Coste and M.-F. Roy; _Géométrie Algébrique Réelle_ ; Springer, 1987.
  * [3] A.P. Calderón and A. Zygmund; _Local properties of solutions of elliptic partial differential equations_ ; Studia Math. 20 (1961), 181-225.
  * [4] L. van den Dries and C. Miller; _Geometric categories and o-minimal structures_ ; Duke Math. J. 84, no 2 (1996), 497-540.
  * [5] G.A. Efroymson; _The extension theorem for Nash functions_ ; Real Algebraic Geometry and Quadratic Forms (Rennes 1981), pp. 343-357, Lecture Notes in Math., 959, Springer 1982.
  * [6] A. Fischer; _Smooth functions in o-minimal structures_ , Adv. Math. 218 (2008), 496-514.
  * [7] B. Kocel-Cynk, W. Pawłucki and A. Valette; _Approximation of singular semialgebraic sets by smooth ones with respect to the Hausdorff metric_ ; Bull. Sci. Math 185 (2023) Paper No. 103270.
  * [8] K. Kurdyka and W. Pawłucki; _Subanalytic version of Whitney’s extension theorem_ ; Studia Math. 124 (1997), 269-280.
  * [9] K. Kurdyka and W. Pawłucki; _O-minimal version of Whitney’s extension theorem_ ; Studia Math. 224 (2014), 81-96.
  * [10] W. Pawłucki; _A linear extension operator for Whitney fields on closed o-minimal sets_ ; Ann. Inst. Fourier (Grenoble) 58 (2008), 383-404.
  * [11] W. Pawłucki; _Lipschitz cell decomposition in o-minimal structures.I_ ; Illinois J. Math. 52 (2008), 1045-1063.
  * [12] D. Pecker; _On Efroymson’s extension theorem for Nash functions_ ; J. Pure Appl. Algebra 37, no 2 (1985), 193-203.
  * [13] M. Shiota; _Approximation theorems for Nash mappings and Nash manifolds_ ; Trans. Amer. Math. Soc., 293, no 1 (1986), 319-337.
  * [14] M.Shiota; _Geometry of subanalytic and semialgebraic sets_ ; Birkhäuser, 1997.
  * [15] E.M. Stein; _Singular Integrals and Differentiability Properties of Functions_ ; Princeton University Press, Princeton, 1970.
  * [16] J.-C. Tougeron; _Idéaux des Fonctions Différentiables_ ; Springer, 1972.
  * [17] A. Valette and G. Valette; _Approximations in globally subanalytic and Denjoy-Carleman classes_ ; Adv. Math. 385 (2021), Paper No. 107764, 32 pp.


#  On regular 2-path Hamiltonian graphs

Xia Lia, Weihua Yanga***Corresponding author. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>(W. Yang)., Bo Zhangb, Shuang Zhaoa
aDepartment of Mathematics, Taiyuan University of Technology, Taiyuan 030024,
China
bDepartment of Mathematics, Shanxi Normal University, Jinzhong 030600, China

Abstract:

Kronk introduced the $l$-path hamiltonianicity of graphs in 1969. A graph is
$l$-path Hamiltonian if every path of length not exceeding $l$ is contained in
a Hamiltonian cycle. We have shown that if $P=uvz$ is a 2-path of a
2-connected, $k$-regular graph on at most $2k$ vertices and $G-V(P)$ is
connected, then there must exist a Hamiltonian cycle in $G$ that contains the
2-path $P$. In this paper, we characterize a class of graphs that illustrate
the sharpness of the bound $2k$. Additionally, we show that by excluding the
class of graphs, both 2-connected, $k$-regular graphs on at most $2k+1$
vertices and 3-connected, $k$-regular graphs on at most $3k-6$ vertices
satisfy that there is a Hamiltonian cycle containing the 2-path $P$ if
$G\setminus V(P)$ is connected.

Keywords

: Hamiltonian cycle; $l$-path Hamiltonian; $k$-regular graph

##  1 Introduction

A _Hamiltonian path $($cycle$)$_ in a graph $G$ is a path (cycle) containing
all the vertices of $G$, and a graph with a Hamiltonian cycle is called
_Hamiltonian_. A graph is _Hamilton-connected_ when every pair of distinct
vertices is connected by a Hamiltonian path. The existence of Hamiltonian
cycles in 2-connected, $k$-regular graphs has been the subject of research in
several publications [4, 2, 6, 16, 3, 10]. The findings of these studies
indicate that all 2-connected, $k$-regular graphs on at most $3k+4$ vertices,
except for two kinds of graphs which is not 3-connected, are Hamiltonian. In
1976, Häggkvist proposed the following conjecture .

######  Conjecture 1 ([5]).

For $k\geqslant 4$, every $m$-connected, $k$-regular graph on at most $(m+1)k$
vertices is Hamiltonian.

The example constructed independently by Jackson and Jung (refer to [7])
provides evidence to refute Conjecture 1 for $m\geqslant 4$. However, there
exists a remaining unresolved case when $m=3$.

######  Conjecture 2 (refer to [7]).

For $k\geqslant 4$, every $3$-connected, $k$-regular graph on at most $4k$
vertices is Hamiltonian.

Considerable progress has been made in investigating the existence of
Hamiltonian cycles within $3$-connected, $k$-regular graphs. Conjecture 2 has
been resolved for significantly large graphs according to [9], but for a very
large (albeit finite) number of cases it remains open. In addition, the proof
provided in [9] is extensive and intricate, making a simpler proof highly
desirable.

Another noteworthy subarea within Hamiltonian graph theory focuses on
Hamiltonian cycles that contain specified elements of a graph. Examples
include $k$-ordered Hamiltonian graphs [14, 13], edge-Hamiltonian graphs [11],
and others. One of these directions is the study of $l$-path Hamiltonicity. A
graph $G$ on $n$ vertices is said to be _$l$ -path Hamiltonian_ if every path
of length not exceeding $l$, $1\leqslant l\leqslant n-2$, is contained in a
Hamiltonian cycle. Kronk in [8] proved that for a graph $G$ on $n$ vertices,
if the sum of the degrees of every pair of non-adjacent vertices of $G$ is at
least $n+l$, where $l$ is a positive integer, then $G$ is $l$-path
Hamiltonian. The idea of combining $l$-path Hamiltonicity with regular graphs
comes from the following result proved by Li in [11].

######  Theorem 3 ([11]).

Let $G$ be a $2$-connected, $k$-regular graph on at most $3k-1$ vertices, and
let $e=uv$ be any edge of $G$ such that $\\{u,v\\}$ is not a cut-set. Then $G$
has a Hamiltonian cycle containing $e$.

Theorem 3 shows that a 2-connected, $k$-regular graph $G$ on at most $3k-1$
vertices satisfying $G-V(P)$ is connected for every path $P$ of length 1 is
1-path Hamiltonian. Motivated by above result, Li and Yang in [12] proved the
following result.

######  Theorem 4 ([12]).

Let $G$ be a $2$-connected, $k$-regular graph on at most $2k$ vertices, and
let $P=uvz$ be any path of $G$ such that $\\{u,v,z\\}$ is not a cut-set. Then
$G$ has a Hamiltonian cycle containing $P$.

From Theorem 3 and Theorem 4, it can be deduced that if a 2-connected,
$k$-regular graph $G$ on at most $2k$ vertices has the property that the graph
$G-V(P)$ is connected for every path $P$ of length at most 2, then $G$ is
2-path Hamiltonian.

For positive integer $q\geqslant k$, we define that a class $\mathscr{H}$ of
graphs of path $P=uvz$ is a 2-connected, $k$-regular graph on $2q+1$ vertices,
which contains two disjoint sets $X$ and $Y$ of vertices such that $Y$ is
independent, $X$ contains $\\{u,v,z\\}$, $|Y|=q$, $|X|=q+1$, $N(Y)\subseteq X$
and $v$ is adjacent to $u$ and $z$. Figure 1 below illustrates a 2-connected,
$k$-regular graph on $2k+1$ vertices belonging to $\mathscr{H}$ with $q=k=4$.

Figure 1:

The existence of the graph class $\mathscr{H}$ demonstrates that the upper
bound $2k$ in Theorem 4 is sharp. Clearly, when $k$ is odd, the class of
graphs $\mathscr{H}$ does not exist. Therefore, it is worthwhile to
investigate whether the result in Theorem 4 can be strengthened by excluding
the graph class $\mathscr{H}$. In this paper, we are going to prove the
following.

######  Theorem 5.

Let $G$ be a $2$-connected, $k$-regular graph on $n$ vertices, and let $P=uvz$
be any path of $G$ such that $\\{u,v,z\\}$ is not a cut-set. If
$G\notin\mathscr{H}$ and $n\leqslant 2k+1$, then $G$ has a Hamiltonian cycle
containing $P$.

The following corollary follows from Theorem 3 and Theorem 5.

######  Corollary 6.

Let $G$ be a $2$-connected, $k$-regular graph on at most $2k+1$ vertices. If
$G-V(P)$ is connected for every path $P$ of length at most $2$ and
$G\notin\mathscr{H}$, then $G$ is $2$-path Hamiltonian.

We present an illustrative example that demonstrates the sharpness of the
bound in Corollary 6. Let $H_{i}$, $i\in\\{1,2\\}$, be a graph which is
obtained from $K_{k+1}$ by deleting one edge $e_{i}=a_{i}b_{i}$. We can
construct a 2-connected, $k$-regular graph $G$ on $2k+2$ vertices from $H_{1}$
and $H_{2}$ by adding $a_{1}a_{2}$ and $b_{1}b_{2}$. Notably, there is a
2-path in $G$ that is not contained in any Hamiltonian cycle of $G$.
Obviously, this example is not 3-connected graph. Is it possible to improve
the result for 3-connected, $k$-regular graphs? In this paper, we also prove
the following.

######  Theorem 7.

Let $G$ be a $3$-connected, $k$-regular graph on $n$ vertices, and let $P=uvz$
be any path of $G$ such that $\\{u,v,z\\}$ is not a cut-set. If
$G\notin\mathscr{H}$ and $n\leqslant 3k-6$, then $G$ has a Hamiltonian cycle
containing $P$.

The following corollary follows from Theorem 3 and Theorem 7.

######  Corollary 8.

Let $G$ be a $3$-connected, $k$-regular graph on at most $3k-6$ vertices. If
$G-V(P)$ is connected for every path $P$ of length at most $2$ and
$G\notin\mathscr{H}$, then $G$ is $2$-path Hamiltonian.

The $L$-graph (as discussed in [11]) as a counterexample of Theorem 3 with
$3k$ vertices is 3-connected for $k\geqslant 6$. Consequently, the bound
provided in Corollary 8 is nearly optimal.

##  2 Notation and preliminaries

All graphs mentioned in this paper are finite simple graphs. For standard
graph theory notation and terminology not explained in this paper, we refer
the reader to [1]. Let $G$ be a graph. $|G|$ and $\delta$ denote the number of
vertices and the minimum degree of $G$, respectively. For $x\in V(G)$ and
$S\subseteq V(G)$, $N_{G}(x)$ denotes the neighbors of $x$ in $G$,
$N_{G}(S)=\bigcup_{x\in S}N_{G}(x)$ and $d_{G}(x)=|N_{G}(x)|$. For a cycle $C$
in $G$ with a fixed orientation, and any two vertices $x,y$ on $C$, we denote
by $x^{+}$ and $x^{-}$ the following vertex and the preceding vertex of $x$
according to the orientation of $C$, respectively. We define the segment
$C[x,y]$ to be the set of vertices on $C$ from $x$ to $y$ (including $x$ and
$y$) according to the orientation and let $C(x,y)=C[x,y]-\\{x,y\\}$.
Analogously, $C[x,y)$ and $C(x,y]$ are also defined. Let $A$ be a set of
vertices of $G$. An $A$-segment is a $C[x,y]$ segment such that $C[x,y]\cap
A=\\{x,y\\}$. We put $x^{+2}=(x^{+})^{+}$ ($x^{-2}=(x^{-})^{-})$ and
$x^{+i}=(x^{+(i-1)})^{+}$ ($x^{-i}=(x^{-(i-1)})^{-})$.

For a cycle $C$ and any $A,B\subseteq V(G)$, let $E(A,B)=\\{uv\in E(G):u\in
A,\ v\in B\\}$ ($E^{{}^{\prime}}(A,B)=\\{uv\in E(G)-E(C):u\in A,v\in B\\}$)
and $E(A)=\\{uv\in E(G):u,v\in A\\}$ ($E^{{}^{\prime}}(A)=\\{uv\in
E(G)-E(C):u,v\in A\\}$). Put $e(A,B)=|E(A,B)|$,
$e^{{}^{\prime}}(A,B)=|E^{{}^{\prime}}(A,B)|$, $e(A)=|E(A)|$ and
$e^{{}^{\prime}}(A)=|E^{{}^{\prime}}(A)|$. For convenience, we often use a
subgraph $H$ of a graph $G$ to denote its vertex set $V(H)$ if no confusion
arises. We shall use the following result.

######  Theorem 9 ([7]).

Let $G$ be a connected graph such that for every longest path $P$ in $G$, the
sum of the degrees of the end-vertices of $P$ is at least $|P|+1$. Then $G$ is
Hamilton-connected.

We first introduce an _operation_ used during the proofs of Theorems 5 and
Theorems 7. Let $G$ be a connected graph on $n$ vertices, and let $P=uvz$ be a
path of $G$. We define a new graph $G_{1}$ by inserting two vertices $w_{1}$
and $w_{2}$ on the edges $e_{1}=uv$ and $e_{2}=vz$ of $P$ respectively. Then
we have
$G_{1}=(G-\\{e_{1},e_{2}\\})\cup\\{w_{1},w_{2}\\}\cup\\{uw_{1},w_{1}v,vw_{2},w_{2}z\\}$,
$P_{1}=uw_{1}vw_{2}z$ and $|G_{1}|=n_{1}=n+2$. Clearly, if we want to prove
that $P$ is contained in a Hamiltonian cycle in $G$, it is sufficient to prove
that $G_{1}$ is Hamiltonian.

##  3 Proof of Theorem 5

From Theorem 4, we have that Theorem 5 holds for $n\leqslant 2k$. So we only
need to consider the case $n=2k+1$. Let $G$ be a 2-connected, $k$-regular
graph on $n=2k+1$ vertices, and let $P=uvz$ be a path of $G$ such that
$\\{u,v,z\\}$ is not a cut-set. After the operation in section 2, we have
$|G_{1}|=n_{1}=2k+3$. Suppose $G_{1}$ is not Hamiltonian. Let $C$ be a longest
cycle of $G_{1}$ containing $w_{1}$ and $w_{2}$, such that the number of
components of $R=G_{1}-C$ is as small as possible. Let $r=|R|$ and
$C=c_{1}c_{2}\cdots c_{n_{1}-r}$. The subscripts of $c_{i}$ will be reduced
modulo $n_{1}-r$ throughout. Obviously, we have $|C|=n_{1}-r\geqslant 6$.

Suppose $R$ is an independent set, then let $v_{0}$ be an isolated vertex in
$R$. Put $Y_{0}=\emptyset$, and for any $j\geqslant 1$,
$X_{j}=N(Y_{j-1}\cup\\{v_{0}\\})$, $Y_{j}=\\{c_{i}\in V(C):c_{i-1},c_{i+1}\in
X_{j}\\}$, $X=\bigcup\limits_{j=1}^{\infty}{{X_{j}}}$,
$Y=\bigcup\limits_{j=0}^{\infty}{{Y_{j}}}$, $x=|X|\geqslant k$ and $y=|Y|$ .
By the hopping lemma ([15]), we have $X\subset V(C),\ X\cap Y=\emptyset$ and
$X$ does not contain two consecutive vertices of $C$. Let
$S_{1},S_{2},\cdots,S_{x}$ be the sets of vertices contained in the open
$X$-segment of $C$ (the sets of vertices on $C$ between $X$ satisfying
$S_{i}\cap X=\emptyset$ for each $i$ with $1\leqslant i\leqslant x$). Put
$\phi=\\{{S_{i}}:\left|{{S_{i}}}\right|\geqslant 2,1\leqslant i\leqslant
x\\}.$ Then $S_{i}=\\{c_{l},c_{l+1},\cdots,c_{m}\\}\in\phi$ is said to be
_$\psi$ -connected_ to $S_{j}=\\{c_{q},c_{q+1},\cdots,c_{z}\\}\in\phi$ if
$\left|{{S_{i}}}\right|$ is odd and $c_{q}$ and $c_{z}$ are both joined to
$c_{l+e}$ for all odd $e$, $1\leqslant e\leqslant m-l-1$. Now,
$c_{l+1},c_{l+3},\cdots,c_{m-1}$ are called _$P$ -vertices_ of $S_{i}$. Set
$P\ =\ \\{c_{i}\in V(C)$: $c_{i}$ is a $P$-vertex of some $S_{j}$ which is
$\psi$-connected to some $S_{t}$ of $\phi$}, and $p=|V(P)|$. By the same proof
as the case 1 in [12], we have the following inequality which is the
inequality (4) in [12],

$p+4\leqslant(n_{1}-2x-k)(n_{1}-1-2x-p)+k-2(r_{1}-1)(x-y-1).$ (1)

From the definition of $P$, we have $p\leqslant\frac{n_{1}-1-2x}{2}$, which
implies $n_{1}-1-2x-p\geqslant 2p-p\geqslant 0$. And $k\geqslant n_{1}-1-2x-p$
by $n_{1}=2k+3$ and $x\geqslant k$. So we have

$p+4\leqslant(n_{1}-2x-k+1)k-2(r_{1}-1)(x-y-1).$ (2)

By the definitions of $X$ and $Y$, we have $x\geqslant y$. Now, we claim
$x\geqslant y+1$. Otherwise, when $x=y$, since
$d_{G_{1}}(w_{1})=d_{G_{1}}(w_{2})=2$, we have $u,v,z$ belong to $X$ and
$w_{1}$, $w_{2}$ belong to $Y$. If $R$ contains at least two isolated
vertices, then $|Y\cup R|\geqslant y+2=x+2$. Because $Y\cup R$ is an
independent set and $N(Y\cup R)\subseteq X$, we have that there are at least
$ky+4=kx+4$ edges from $Y\cup R$ to $X$, but $X$ accepts at most $kx$ edges, a
contradiction. So, when $x=y$, $R$ contains only one isolated vertex, which
implies $n_{1}=2x+1$ and $n=2x-1=2q+1$ for $q=x-1$. By definition of
$\mathscr{H}$, we have $G\in\mathscr{H}$, a contradiction. Therefore by (2),
we have $n_{1}-2x-k+1>0$, and then $n_{1}>3k-1\geqslant 3k$, which contradicts
$n_{1}=2k+3$.

Thus in the following proof, we assume that there exists a component $H$ in
$R$ such that $|H|\geqslant 2$. For a path
$Q={q_{1}}{q_{2}}\cdots{q_{g}},g\geqslant 2$, in $H$, let $t(Q)$ denote the
number of $C[c_{i},c_{j}]$ such that $c_{i}$ is joined to one of $q_{1}$ and
$q_{g}$, $c_{j}$ is joined to the other, and
$e(\left\\{{{q_{1}},{q_{g}}}\right\\},\\{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}\\})=0$.
We say that $Q$ satisfies the condition $(*)$ if $t(Q)\geqslant 2$,
${N_{C}}(\left\\{{{q_{1}},{q_{g}}}\right\\})\not\subset\left\\{{u,v,z}\right\\}$
and there is a $C[c_{i},c_{j}]$ such that $u,v,z,{w_{1}}\ $and$\
{w_{2}}\notin\left\\{{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}}\right\\}$. Now,
let $H$ be the largest component of $R$ and $h=|H|$. The rest of the proof of
Theorem 5 is divided into two cases. We first consider the case of $k\geqslant
6$, and we prove it in the following two cases.

$\bf Case\ 1.$ $2\leqslant h\leqslant k$.

######  Claim 1.

For $k\geqslant 6$, if $2\leqslant h\leqslant k$, then $H$ is Hamilton-
connected.

###### Proof.

By contradiction, suppose $H$ is not Hamilton-connected. From Theorem 9, we
can choose a longest path $Q={q_{1}}{q_{2}}\cdots{q_{g}},g\geqslant 2$, in
$H$, satisfying ${d_{H}}({q_{1}})+{d_{H}}({q_{g}})\leqslant|Q|=g$. For any
$v\in V(H)$, since $h\leqslant k$, we have ${N_{C}}({v})\geqslant 1$. Let
$X={N_{C}}({q_{1}})\cap{N_{C}}({q_{g}})$ and $|X|=x$.

First, we prove that ${N_{C}}({q_{1}})={N_{C}}({q_{g}})$. Otherwise, without
loss of generality assume that ${d_{C}}({q_{1}})\leqslant{d_{C}}({q_{g}})$. If
${d_{C}}({q_{1}})=1$, we have ${d_{C}}({q_{g}})\geqslant 2k-g-1$ since
${d_{C}}({q_{1}})+{d_{C}}({q_{g}})\geqslant 2k-g$. Since $C$ is the longest
cycle of $G_{1}$ containing $w_{1}$ and $w_{2}$, we have that every
${N_{C}}({q_{g}})$-segment of $C$ contains at least one interior vertex. Hence
$n_{1}\geqslant|H|+|C|\geqslant g+2{d_{C}}({q_{g}})\geqslant
g+2(2k-g-1)=4k-g-2\geqslant 3k-2$, a contradiction. Thus, we have
$2\leqslant{d_{C}}({q_{1}})\leqslant{d_{C}}({q_{g}})$. It is easy to prove
that $t(Q)\geqslant 2$ and $x+1\leqslant t(Q)$. Since ${N_{C}}(\\{q_{1},\
q_{g}\\})\cup({N_{C}}(\\{q_{1},\ q_{g}\\}))^{+}\cup H\subseteq V(G_{1})$, we
have

$\begin{array}[]{l}n_{1}\geqslant\left|C\right|+\left|H\right|\geqslant\left|H\right|+2|{N_{C}}(\\{q_{1},\
q_{g}\\})|+(t(Q)-2)(g-1)\\\ \ \ \ \ \geqslant
g+2[{d_{C}}({q_{1}})+{d_{C}}({q_{g}})]-2|{N_{C}}({q_{1}})\cap{N_{C}}({q_{g}})|+(t(Q)-2)(g-1)\\\
\ \ \ \ \geqslant g+2(2k-g)-2x+(t(Q)-2)(g-1)\\\ \ \ \ \ \geqslant
4k-g-2(x+1)+2+(t(Q)-2)(g-1)\\\ \ \ \ \ \geqslant 4k-g-2t(Q)+2+(t(Q)-2)(g-1)\\\
\ \ \ \ \geqslant 3k-2+(t(Q)-2)(g-3).\end{array}$

Since H is not Hamilton-connected, we have $g\geqslant 3$. This implies
$(t(Q)-2)(g-3)\geqslant 0$. Therefore, we have $n_{1}\geqslant 3k-2$, a
contradiction.

From the above discussion, we have ${N_{C}}({q_{1}})={N_{C}}({q_{g}})=X$ and
$t(Q)=x={d_{C}}({q_{1}})={d_{C}}({q_{g}})\geqslant
k-\frac{g}{2}\geqslant\frac{k}{2}\geqslant 3$. Then

$\begin{array}[]{l}n_{1}\geqslant\left|C\right|+\left|H\right|\geqslant(t(Q)-2)g+2+t(Q)+h\geqslant(x-2)g+2+x+g\\\
\ \ \ \ \geqslant(x-1)(g+1)+3\geqslant(k-\frac{g}{2}-1)(g+1)+3.\end{array}$

Since $f(g)=(k-\frac{g}{2}-1)(g+1)+3$ is a concave function of $g$,
$3\leqslant g\leqslant k$, we have $f(3)=4k-7>2k+3$ and
$f(k)=\frac{k^{2}}{2}-\frac{k}{2}+2>2k+3$ when $k\geqslant 6$. Hence
$f(g)>2k+3$, a contradiction.

∎

$\bf Subcase\ 1.1.$ $h=k$.

If there is a $N_{C}(H)$-segment $C[c_{i},c_{j}]$ such that $u,v,z,{w_{1}}\
$and$\ {w_{2}}\notin\left\\{{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}}\right\\}$,
we have $|C(c_{i},c_{j})|\geqslant h$ and
$n_{1}\geqslant|H|+|C|\geqslant|H|+|C(c_{i},c_{j})|+|\\{v,w_{1},w_{2},c_{i},c_{j}\\}|\geqslant
h+h+5=2k+5$, a contradiction. Thus, $|N_{C}(H)|=2$ and $v\in N_{C}(H)$. Let
$X=N_{C}(H)$. Since $h=k$, for any $v_{i}\in H,\ i\in\\{1,\cdots,h\\}$, we
have $|{N_{C}}({v_{i}})|\geqslant 1$. So $e(H,X)\geqslant k$. Because
$|G_{1}-H-X|=n_{1}-k-2=2k+3-k-2=k+1$, we have

$e(G_{1}-H-X)=e(G_{1}-H-X-\\{w_{1},w_{2}\\})+e(G_{1}-H-X,\\{w_{1},w_{2}\\})\leqslant\frac{(k-2)(k-1)}{2}+2.$

Since $G$ is a $k$-regular graph, we have

$e(G_{1}-H-X,X)=k|G_{1}-H-X-\\{w_{1},w_{2}\\}|+4-2e(G_{1}-H-X)-e(G_{1}-H-X,H).$

Since $e(G_{1}-H-X,H)=0$, we have

$e(G_{1}-H-X,X)\geqslant k(k-1)+4-2(\frac{(k-2)(k-1)}{2}+2)=2k-2\geqslant
k+1.$

On the other hand $e(G_{1}-H-X,X)\leqslant e(G_{1},X)-e(H,X)\leqslant 2k-k=k$,
a contradiction.

$\bf Subcase\ 1.2.$ $\frac{k+1}{2}\leqslant h\leqslant k-1$.

Since $H$ is Hamilton-connected, it is easy to deduce that there exists a
Hamiltonian path $Q$ in $H$ such that $Q$ satisfies $(*)$. By a similar proof
to Lemma 6 in [12], we have the following claim.

######  Claim 2.

There exists a Hamiltonian path $Q$ in $H$ such that $t(Q)\geqslant 3$.

Since $t(Q)\geqslant 3$, there is a $C[c_{i},c_{j}]$ such that $u,v,z,{w_{1}}\
$and$\ {w_{2}}\notin\left\\{{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}}\right\\}$.
Then there exists either ${c_{i}^{-}}\notin\\{{w_{1}},{w_{2}}\\}$ or
${c_{j}^{+}}\notin\\{{w_{1}},{w_{2}}\\}$. Without loss of generality, let
${c_{i}^{-}}\notin\\{{w_{1}},{w_{2}}\\}$. Since $C$ is a longest cycle of
$G_{1}$ containing $w_{1}$ and $w_{2}$, we have
${N_{G_{1}}}({c_{i}^{-}})\cap\left[{H\cup{{c_{j-1}},{c_{j-2}},\cdots,{c_{j-h}}}\cup\left\\{{c_{i}^{-}}\right\\}}\right]=\emptyset$.
And there are at least two of $\\{v,w_{1},w_{2}\\}$ which can not be adjacent
to ${c_{i}^{-}}$. This implies ${d_{G_{1}}}({c_{i}^{-}})\leqslant
2k+3-({h+h+3})\leqslant k-1$, a contradiction to ${d_{G_{1}}}({c_{i}^{-}})=k$.

$\bf Subcase\ 1.3.$ $2\leqslant h\leqslant\frac{k}{2}$.

For any $v\in V(H)$, since $2\leqslant h\leqslant\frac{k}{2}$, we have
${N_{C}}({v})\geqslant k-h+1\geqslant k-\frac{k}{2}+1\geqslant 4$. So
$N_{C}(H)\geqslant k-h+1$. Let $a\in V(H)$ and ${N_{C}}({a})=A$.

######  Claim 3.

For any $A$-segment $C[c_{i},c_{j}]$ satisfying
$C[c_{i},c_{j}]\cap\\{w_{1},w_{2}\\}=\emptyset$, we have $C[c_{i},c_{j}]\cap
N_{C}((V(H)-a))\neq\emptyset$.

###### Proof.

Let $N_{C}((V(H)-a))=S$. Suppose that there is an $A$-segment $C[c_{i},c_{j}]$
satisfying $C[c_{i},c_{j}]\cap[\\{w_{1},w_{2}\\}\cup S]=\emptyset$. Let
$S=\left\\{{{c_{{r_{1}}}},{c_{{r_{2}}}},\cdots,{c_{{r_{s}}}}}\right\\}$, where
${c_{{r_{1}}}}$ and ${c_{{r_{s}}}}$ are the closest vertices to $c_{j}$ and
$c_{i}$ in $S$, respectively. Clearly, $|S|=s\geqslant k-h+1\geqslant 4$.
Therefore, there is at least one segment of $C[c_{j},c_{r_{1}}]$ and
$C[c_{r_{s}},c_{i}]$ which does not contain $w_{1}$ and $w_{2}$. Without loss
of generality, let $w_{1},\ w_{2}\notin C[c_{r_{s}},c_{i}]$. Obviously, we
have
${N_{C}}(c_{i}^{+})\cap\left[{H\cup\left\\{{c_{r_{s}+1},c_{r_{s}+2},\cdots,c_{r_{s}+h},{w_{1}},{w_{2}},{c_{i}^{+}}}\right\\}}\right]=\emptyset$.
And for any $C[c_{r_{i}},c_{r_{i+1}}]$ satisfying
$C[c_{r_{i}},c_{r_{i+1}}]\cap\\{w_{1},\ w_{2}\\}=\emptyset$ ,
$i\in\\{1,2,\cdots,s-1\\}$, we have
${N_{C}}(c_{i}^{+})\cap\\{c_{r_{i}+1},c_{r_{i}+2}\\}=\emptyset$. This implies

$\begin{array}[]{l}d_{G_{1}}({c_{i}^{+}})\leqslant 2k+3-[h+2(s-2-1)+h+3]\\\ \
\ \ \ \ \ \ \ \ \ \ \leqslant 2k+3-[h+2(k-h+1-2-1)+h+3]\leqslant
4,\end{array}$

a contradiction. ∎

By Claim 3, we have

$\left|C\right|\geqslant|A|+(|A|-2)h+2\geqslant(k-h+1)+(k-h+1-2)h+2$ (3)

and
$n_{1}\geqslant\left|C\right|+\left|H\right|\geqslant(k-h+1)+(k-h+1-2)h+2+h=k+3+(k-h-1)h$.

Put $g(h)=k+3+(k-h-1)h$. For $k\geqslant 7$, since $g(h)$ is a concave
function of $h$ with $g(2)=3k-3>2k+3$ and
$g(\frac{k}{2})=\frac{k^{2}}{4}+\frac{k}{2}+3>2k+3$. Hence $g(h)>2k+3$, a
contradiction. When $k=6$ and $n_{1}=15$, there are two cases where $h=2$ and
$h=3$ to consider as follows.

Case (a): $h=2$. By (3), we have
$13=n_{1}-h\geqslant|C|\geqslant(k-h+1)+(k-h+1-2)h+2=13$. So $R$ has only one
component $H$ and $|C|=|A|+(|A|-2)h+2=13$. Since $C$ is a longest cycle of
$G_{1}$ containing $w_{1}$ and $w_{2}$, we have
$N_{C}(v_{i})=N_{C}(v_{j}),i\neq j$, for any $v_{i}\in H,i\in\\{1,2\\}$. Let
$N_{C}(H)=X$ and $Z=X^{+}\cup X^{-}$. Clearly, we have $u,v,z\in X$ and
$e^{{}^{\prime}}(Z)=0$, otherwise, there exists a longer cycle containing
$w_{1}$ and $w_{2}$. Since $e(Z,H)=0$, $|X|=5$ and $|Z|=8$, we have
$e(Z,X)=(6-1)\times 6+4=34$. However, $e(Z,X)\leqslant k|X|-e(H,X)\leqslant
20$, a contradiction.

Case (b): $h=3$. It is similar to case (a) above.

The following figure 2 shows the edges between $H$ and $C$ in the above two
cases.

Figure 2:

$\bf Case\ 2.$ $h\geqslant k+1.$

By the assumption of connectivity and as $\\{u,v,z\\}$ is not a cut-set, there
exists $x{{}^{\prime\prime}}\in{N_{C}}(H)$, such that
$x^{{}^{\prime\prime}-}\notin\\{w_{1},w_{2}\\}$. It is clear that
${N_{G_{1}}}({x^{{}^{\prime\prime}-}})\cap{H}=\emptyset$, and at least two of
$\\{v,w_{1},w_{2}\\}$ cannot be adjacent to $x^{{}^{\prime\prime}-}$. It
follows that $d_{G_{1}}(x^{{}^{\prime\prime}-})\leqslant 2k+3-(k+1)-2-1=k-1$,
a contradiction.

These contradictions complete our proof for $k\geqslant 6$. We next discuss
the case of $3\leqslant k\leqslant 5$. Since $2k+1$ is odd, we only need to
discuss the cases of $k=4$. When $k=4$, we have $n_{1}=11$. Since
$|C|\geqslant 6$, we consider the following four cases. It is worth noting
that we have already proved the case when $R$ is an independent set in the
preceding paragraph. Now, we first prove a simple claim.

######  Claim 4.

When $k=4$, if $R$ contains an edge $v_{0}v_{1}$ and $|C|\leqslant 9$, then
$N_{C}(v_{0})=N_{C}(v_{1})$.

###### Proof.

By contradiction. Let $Q=v_{0}v_{1}$. Suppose $N_{C}(v_{0})\neq N_{C}(v_{1})$,
and without loss of generality, $|N_{C}(v_{0})-N_{C}(v_{1})|=1$. Since $G$ is
a 4-regular graph, we have $|N_{C}(v_{0})\cup N_{C}(v_{1})|=4$ and $t(Q)=4$.
Since $C$ is a longest cycle of $G_{1}$ containing $w_{1}$ and $w_{2}$, we
have$|C|\geqslant|N_{C}(v_{0})\cup N_{C}(v_{1})|+2(t(Q)-2)+2\geqslant 10$, a
contradiction. ∎

Case (a): $|V(C)|=9$. Let $C=uw_{1}vw_{2}zx_{1}x_{2}x_{3}x_{4}$. Then $R$ is
an edge $v_{0}v_{1}$. By Claim 4 , we have ${N_{C}}(v_{0})={N_{C}}(v_{1})$. By
assumption and symmetry, we have ${N_{C}}(R)=\\{v,z,x_{3}\\}$,
${N_{C}}(R)=\\{v,z,x_{4}\\}$, or ${N_{C}}(R)=\\{x_{1},x_{4},v\\}$. If
${N_{C}}(R)=\\{x_{1},x_{4},v\\}$, we have $x_{2}u\notin E(G_{1})$, otherwise,
there is a Hamiltonian cycle
$C^{\prime}=v_{0}x_{1}zw_{2}vw_{1}ux_{2}x_{3}x_{4}v_{1}$. So we have
${d_{G_{1}}}(x_{2})\leqslant 3$, a contradiction. The proofs for
${N_{C}}(R)=\\{v,z,x_{3}\\}$ and ${N_{C}}(R)=\\{v,z,x_{4}\\}$ are similar.

Case (b): $|V(C)|=8$. Let $C=uw_{1}vw_{2}zx_{1}x_{2}x_{3}$.

Subcase (b1): $R$ consists of an edge $v_{0}v_{1}$ and an isolated vertex
$v_{2}$. By Claim 4 , we have ${N_{C}}(v_{0})={N_{C}}(v_{1})$. By assumption
and symmetry, we have ${N_{C}}(v_{0})={N_{C}}(v_{1})=\\{v,z,x_{3}\\}$. Since
$v\in{N_{C}}(v_{2})$, we have ${d_{G_{1}}}(v)\geqslant 5$, a contradiction.

Subcase (b2): $R$ contains only one connected component $H$ which has three
vertices. Since $G$ is a 4-regular graph, we have ${d_{C}}(H)\geqslant 6$ and
$|{N_{C}}(H)|\geqslant 3$. By assumption and symmetry, we have
$\\{v,z,x_{2}\\}\subseteq{N_{C}}(H)$, $\\{v,z,x_{3}\\}\subseteq{N_{C}}(H)$,
$\\{u,z,x_{2}\\}\subseteq{N_{C}}(H)$ or
$\\{v,x_{1},x_{3}\\}\subseteq{N_{C}}(H)$. If
$\\{v,z,x_{2}\\}\subseteq{N_{C}}(H)$, we have $x_{1},x_{3}\notin{N_{C}}(H)$.
We claim $x_{1}x_{3}\notin E(G_{1})$, otherwise, there is a longer cycle
$C^{\prime}=Hzw_{2}vw_{1}ux_{3}x_{1}x_{2}$ containing $w_{1}$ and $w_{2}$.
Since $G$ is a 4-regular graph, we have $v\in{N_{G_{1}}}(x_{1})$ and
$v\in{N_{G_{1}}}(x_{3})$, ${d_{G_{1}}}(v)\geqslant 5$, a contradiction. The
proofs for the other three cases are similar.

Case (c): $|V(C)|=7$. Let $C=uw_{1}vw_{2}zx_{1}x_{2}$. Clearly, there cannot
have isolated vertex in $R$.

Subcase (c1): $R$ consists of two edges $v_{0}v_{1}$ and $v_{2}v_{3}$ that are
not in the same component. By Claim 4 , we have
$v\in{N_{C}}(v_{i}),i=0,1,2,3$, implying ${d_{G_{1}}}(v)\geqslant 6$, a
contradiction.

Subcase (c2): $R$ contains only one connected component $H$ which has four
vertices. Since $G$ is a 4-regular graph, we have ${d_{C}}(H)\geqslant 4$ and
$|{N_{C}}(H)|\geqslant 2$. By assumption and symmetry, we have
$\\{v,x_{1}\\}\subseteq{N_{C}}(H)$ or $\\{z,x_{2}\\}\subseteq{N_{C}}(H)$. If
$\\{v,x_{1}\\}\subseteq{N_{C}}(H)$, we have $z,x_{2}\notin{N_{C}}(H)$. Since
$G$ is a 4-regular graph, we have $vx_{2},zx_{2}\in E(G_{1})$. So $v$ can
accept at most 1 edge from $H$. Then ${N_{C}}(H)\geqslant 3$ and
$u\in{N_{C}}(H)$. There is a longer cycle
$C^{\prime}=Huw_{1}vw_{2}zx_{2}x_{1}$ containing $w_{1}$ and $w_{2}$, a
contradiction. The proof for $\\{z,x_{2}\\}\subseteq{N_{C}}(H)$ is similar.

Case (d): $|V(C)|=6$. Let $C=uw_{1}vw_{2}zx_{1}$. Clearly, there is no
component $H$ in $R$ such that $|H|=1$ or $|H|=2$. So $R$ contains only one
connected component $H$ which has five vertices. Obviously, there exist two
consecutive vertices of $\\{u,z,x_{1}\\}$ which are adjacent to $H$, a
contradiction.

Thus, we complete the proof of Theorem 5.

##  4 Proof of Theorem 7

Let $G$ be a 3-connected, $k$-regular graph on $n\leqslant 3k-6$ vertices, and
let $P=uvz$ be a path of $G$ such that $\\{u,v,z\\}$ is not a cut-set. After
the operation in section 2, we have $|G_{1}|=n_{1}\leqslant 3k-4$. From
Theorem 4, we have $3k-6\geqslant 2k+1$, so, $k\geqslant 7$. Suppose $G_{1}$
is not Hamiltonian. Let $C$ be a longest cycle of $G_{1}$ containing $w_{1}$
and $w_{2}$, such that the number of components of $R=G_{1}-C$ is as small as
possible. Let $r=|R|$ and $C=c_{1}c_{2}\cdots c_{n_{1}-r}$. The subscripts of
$c_{i}$ will be reduced modulo $n_{1}-r$ throughout. Obviously, we have
$|C|=n_{1}-r\geqslant 7$.

When $R$ is an independent set, by the same proof as in section 3, we get
$n_{1}\geqslant 3k$, which contradicts $n_{1}\leqslant 3k-4$. Thus in the
following proof, we assume that there exists a component $H$ in $R$ such that
$|H|\geqslant 2$. For a path $Q={q_{1}}{q_{2}}\cdots{q_{g}},g\geqslant 2$, in
$H$, let $t(Q)$ denote the number of $C[c_{i},c_{j}]$ such that $c_{i}$ is
joined to one of $q_{1}$ and $q_{g}$, $c_{j}$ is joined to the other, and
$e(\left\\{{{q_{1}},{q_{g}}}\right\\},\\{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}\\})=0$.
We say that $Q$ satisfies the condition $(*)$ if $t(Q)\geqslant 2$,
${N_{C}}(\left\\{{{q_{1}},{q_{g}}}\right\\})\not\subset\left\\{{u,v,z}\right\\}$
and there is a $C[c_{i},c_{j}]$ such that $u,v,z,{w_{1}}\ $and$\
{w_{2}}\notin\left\\{{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}}\right\\}$. Now,
let $H$ be the largest component of $R$ and $h=|H|$. Consider the following
three cases.

$\bf Case\ 1.$ $2\leqslant h\leqslant k$.

By the same proof as in claim 1, if $H$ is not Hamilton-connected, we have
$n_{1}\geqslant(k-\frac{g}{2}-1)(g+1)+3$. Since
$f(g)=(k-\frac{g}{2}-1)(g+1)+3$ is a concave function of $g$, $3\leqslant
g\leqslant k$, we have $f(3)=4k-7>3k-4$ and
$f(k)=\frac{k^{2}}{2}-\frac{k}{2}+2>3k-4$ when $k\geqslant 7$. Hence
$f(g)>3k-4$, a contradiction. Then $H$ is Hamilton-connected.

Let $M=\\{r_{i}x_{i}\in E(G_{1}):i\in\\{1,\ 2,\cdots,\ m\\},\ r_{i}\in V(H),\
x_{i}\in V(C)\\}$ be a maximum matching in $E_{G_{1}}(H,C)$ and $m=|M|$, then
$m\geqslant 3$ since $G$ is 3-connected. In order to prove case 1, we next
consider the following two subcases.

$\bf Subcase\ 1.1.$ $k-2\leqslant h\leqslant k$.

We claim $m=3$. Otherwise, suppose $m\geqslant 4$, we must have
$n_{1}\geqslant|H|+|C|\geqslant h+m+(m-2)h+2\geqslant h+2+2h+4=3h+6\geqslant
3(k-2)+6=3k$, a contradiction.

Let $x_{1},\ x_{2},\ x_{3}$ be in this order on $C$. Since $\\{u,v,z\\}$ is
not a cut-set, without loss of generality, let $x_{3}\notin\\{u,\ w_{1},\ v,\
w_{2},\ z\\}$ and $x_{3}^{-}\notin\\{{w_{1},w_{2}}\\}$,
$x_{3}^{+}\notin\\{{w_{1},w_{2}}\\}$. Then we have either $C[x_{3},x_{1}]$ or
$C[x_{2},x_{3}]$ which does not contain $w_{1}$ and $w_{2}$. When
${w_{1},w_{2}}\notin C[x_{3},x_{1}]$, since $C$ is a longest cycle of $G_{1}$
containing $w_{1}$ and $w_{2}$, we have

${N_{C}}(x_{3}^{-})\cap\left[{H\cup\left\\{x_{1}^{-},x_{1}^{-2}\cdots,x_{1}^{-h}\right\\}\cup
x_{3}^{-}}\right]=\emptyset.$

And there are at least two of $\\{v,w_{1},w_{2}\\}$ which can not be adjacent
to $x_{3}^{-}$. It follows that

${d_{G_{1}}}(x_{3}^{-})\leqslant 3k-4-2h-3\leqslant 3k-4-2(k-2)-3=k-3,$

this contradicts ${d_{G_{1}}}(x_{3}^{-})=k$. When ${w_{1},w_{2}}\notin
C[x_{2},x_{3}]$, we have

${N_{C}}(x_{3}^{+})\cap\left[{H\cup\left\\{x_{2}^{+},x_{2}^{+2}\cdots,x_{2}^{+h}\right\\}\cup
x_{3}^{+}}\right]=\emptyset.$

And there are at least two of $\\{v,w_{1},w_{2}\\}$ which can not be adjacent
to $x_{3}^{+}$. It follows that

${d_{G_{1}}}(x_{3}^{+})\leqslant 3k-4-2h-3\leqslant 3k-4-2(k-2)-3=k-3,$

this contradicts ${d_{G_{1}}}(x_{3}^{+})=k$.

$\bf Subcase\ 1.2.$ $2\leqslant h\leqslant k-3$.

For any $v\in V(H)$, since $2\leqslant h\leqslant k-3$, we have
${N_{C}}({v})\geqslant k-h+1\geqslant 4$. By a similar proof as in Case 1.3,
we have $n_{1}\geqslant\left|C\right|+\left|H\right|\geqslant k+3+(k-h-1)h.$
Put $g(h)=k+3+(k-h-1)h$. Since $g(h)$ is a concave function of $h$ with
$g(2)=3k-3=g(k-3)$. Hence $g(h)>3k-4$, a contradiction.

$\bf Case\ 2.$ $k+1\leqslant h\leqslant 2k-7$.

Let $Q={q_{1}}{q_{2}}\cdots{q_{g}}$ be a path in $H$, which is chosen as long
as possible such that $Q$ satisfies the condition $(*)$ (note that we are
assuming 3-connectedness and that $\\{u,v,z\\}$ is not a cut-set). Put
$A={N_{C}}({q_{1}})$ and $B={N_{C}}({q_{g}})$.

######  Claim 5.

$2\leqslant g\leqslant k-8$.

###### Proof.

Suppose that $g\geqslant k-7$. By the definition of the condition $(*)$, there
is a $C[c_{i},c_{j}]$ such that $u,v,z,{w_{1}}\ and\
{w_{2}}\notin\left\\{{{c_{i+1}},{c_{i+2}},\cdots,{c_{j-1}}}\right\\}$. By the
assumption of 3-connectedness and as $\\{u,v,z\\}$ is not a cut-set, we have
either $c_{i}^{-}\notin\\{w_{1},w_{2}\\}$ or
$c_{j}^{+}\notin\\{w_{1},w_{2}\\}$. Without loss of generality, let
$c_{i}^{-}\notin\\{w_{1},w_{2}\\}$. We have
${N_{C}}(c_{i}^{-})\cap\\{H\cup\\{{c_{i}^{-},{c_{j-1},c_{j-2},\cdots,c_{j-g}}}\\}\\}=\emptyset$,
and at least two of $\\{v,w_{1},w_{2}\\}$ cannot be adjacent to $c_{i}^{-}$.
Thus

${d_{G_{1}}}(c_{i}^{-})\leqslant 3k-4-\left[{h+g+2+1}\right]\leqslant
3k-4-(k+1)-(k-7)-2-1\leqslant k-1.$

This contradicts that ${d_{G_{1}}}(c_{i}^{-})=k$. ∎

######  Claim 6.

$Q$ is a maximal path in $H$ satisfying $(*)$.

###### Proof.

Suppose that $Q$ is not a maximal path in $H$.

Let
$Q^{\prime}={b_{1}}{b_{2}}\cdots{b_{s}}{q_{1}}{q_{2}}\cdots{q_{g}}{q_{g+1}}\cdots{q_{e}}$
be a maximal path in $H$ containing $Q$. Without loss of generality, we assume
$s\geqslant 1$. From the definition of $Q$, we have $N_{C}(b_{1})\leqslant 3$,
which implies $N_{H}({b_{1}})\geqslant k-3$.

When $N_{H}(b_{1})\cap\\{q_{2},q_{3},\cdots,q_{e}\\}\neq\emptyset$, one of the
following three cases occurs.

  1. (1).

$N_{H}(b_{1})\cap\\{q_{g+1},q_{g+2},\cdots,q_{e}\\}=\emptyset$.

  2. (2).

$N_{H}(b_{1})\cap\\{q_{2},q_{3},\cdots,q_{g-1}\\}=\emptyset$.

  3. (3).

$N_{H}(b_{1})\cap\\{q_{g+1},q_{g+2},\cdots,q_{e}\\}\neq\emptyset$ and
$N_{H}(b_{1})\cap\\{q_{2},q_{3},\cdots,q_{g-1}\\}\neq\emptyset$.

In (1), set $i=min\\{j\geqslant 2:b_{1}q_{j}\in E(G_{1})\\}$. Let
$Q^{\prime\prime}={q_{1}}{b_{s}}{b_{s-1}}\cdots{b_{1}}{q_{i}}{q_{i+1}}\cdots{q_{g}}$.
In (2), set $j=max\\{d\geqslant g:b_{1}q_{d}\in E(G_{1})\\}$. Let
$Q^{\prime\prime}={q_{1}}{b_{s}}{b_{s-1}}\cdots{b_{1}}{q_{j}}{q_{j-1}}\cdots{q_{g}}$.
In both (1) and (2), since $N_{H}(b_{1})\cup\\{b_{1}\\}\subseteq
Q^{\prime\prime}$, then $g\geqslant|V(Q^{\prime\prime})|\geqslant k-2$, a
contradiction to Claim 5.

In (3), set

$l_{1}=min\\{j:2\leqslant j\leqslant g-1,b_{1}q_{j}\in E(G_{1})\\},$
$l_{2}=max\\{j:2\leqslant j\leqslant g-1,b_{1}q_{j}\in E(G_{1})\\},$

and

$l_{3}=max\\{j:b_{1}q_{j}\in E(G_{1})\\}.$

Let
$Q^{*}={q_{1}}{b_{s}}{b_{s-1}}\cdots{b_{1}}{q_{l_{1}}}{q_{l_{1}+1}}\cdots{q_{g}}$
and
$Q^{**}={q_{1}}{q_{2}}\cdots{q_{l_{2}}}{b_{1}}{q_{l_{3}}}{q_{l_{3}-1}}\cdots{q_{g}}$.
Because $g\geqslant max\\{|V(Q^{*})|,|V(Q^{**})|\\}$, we have
$l_{1}-2\geqslant s$ and $g-1-l_{2}\geqslant l_{3}-g+1$, which implies
$g\geqslant(l_{2}-l_{1}+1)+s+l_{3}-g+1+2$. So

$\begin{array}[]{l}g\geqslant
1+|\\{b_{1},\cdots,{b_{s}}\\}\cup\\{q_{1},{q_{g}}\\}\cup\\{{q_{l_{1}}},{q_{l_{1}+1}},\cdots,{q_{l_{2}}}\\}\cup\\{{q_{g+1}},\cdots,{q_{l_{3}}}\\}|\\\
\ \ \ \geqslant 1+|N_{H}(b_{1})\cup\\{b_{1}\\}|\geqslant k-1,\end{array}$

a contradiction to Claim 5.

A similar argument holds if
$N_{H}(q_{e})\cap\\{b_{1},b_{2},\cdots,b_{s},q_{1},q_{2},\cdots,q_{g-1}\\}\neq\emptyset$.
Thus it is enough for completing our proof to discuss the following two cases.

  1. (a).

$e>g,~{}N_{H}(b_{1})\subseteq\\{b_{2},b_{3},\cdots,b_{s},q_{1}\\}$ and
$N_{H}(q_{e})\subseteq\\{q_{g},q_{{g+1}},\cdots,q_{{e-1}}\\}$

  2. (b).

$e=g,~{}N_{H}(b_{1})\subseteq\\{b_{2},b_{3},\cdots,b_{s},q_{1}\\}$ .

In case (a), since $|N_{C}(b_{1})|\leqslant 3$, we have
$|\\{b_{1},\cdots,{b_{s}}\\},q_{1}|\geqslant|N_{H}(b_{1})\cup\\{b_{1}\\}|\geqslant
k-2$. Similarly
$|\\{q_{g},\cdots,{q_{e-1}}\\},q_{e}|\geqslant|N_{H}(q_{e})\cup\\{q_{e}\\}|\geqslant
k-2$. Then we have
$|H|\geqslant|N_{H}(b_{1})\cup\\{b_{1}\\}|+|N_{H}(q_{e})\cup\\{q_{e}\\}|\geqslant
2k-4$. This contradicts $k+1\leqslant h\leqslant 2k-7$.

In case (b), denote $q_{1}=b_{s+1}$. Let $i=max\\{j:b_{1}b_{j}\in
E(G_{1})\\}$. We claim that $N_{C}(b_{l})=\\{v\\}$ and
$N_{H}(b_{l})\cap\\{q_{2},q_{3},\cdots,q_{g}\\}=\emptyset$, for any
$1\leqslant l\leqslant i-1$. Otherwise, let
$d=min\\{j:j>l~{}and~{}b_{1}b_{j}\in E(G_{1})\\}$. When
$|N_{C}(b_{l})|\geqslant 2$, either
${b_{l}}{b_{l-1}}\cdots{b_{1}}{b_{d}}{b_{d+1}}\cdots{b_{s}}{q_{1}}$ or
${b_{l}}{b_{l-1}}\cdots{b_{1}}{b_{d}}{b_{d+1}}\cdots{b_{s}}{q_{1}}{q_{2}}\cdots{q_{g}}$
is a path that satisfies $(*)$ and is longer than $Q$, a contradiction. When
$q_{f}\in N_{H}(b_{l})$ for some $2\leqslant f\leqslant g$, then

${Q^{\prime\prime\prime}=q_{1}}{b_{s}}{b_{s-1}}\cdots{b_{d}}{b_{1}}{b_{2}}\cdots{b_{l}}{q_{f}}{q_{f+1}}\cdots{q_{g}}$

is the path that satisfies $(*)$ and is longer than $Q$, a contradiction.

Since $|Q^{\prime}|\geqslant|N_{H}(b_{1})|+|N_{H}(q_{g})|+2-1$, we have

$\begin{array}[]{l}n_{1}\geqslant|Q^{\prime}|+|C|\\\ \ \ \ \
\geqslant|N_{H}(b_{1})|+k-|B|+1+|B|+(|B|-1+g)\\\ \ \ \ \
\geqslant|N_{H}(b_{1})|+k+|B|+g\\\ \ \ \ \ \geqslant 2k-1+|B|+g.\end{array}$

So $g\leqslant 3k-4-2k+1-|B|<k-|B|=|N_{H}(q_{g})|$. It follows that
$N_{H}(q_{g})\cap\\{{b_{1}},{b_{2}},\cdots,{b_{s}}\\}\neq\emptyset$. Then
$|N_{C}(q_{2})|\leqslant 3$ as there is a path in $H$ with at least $g+1$
vertices connecting $q_{1}$ and $q_{2}$, a contradiction. Thus we have
$|H|\geqslant|N_{H}(b_{1})|+|N_{H}(q_{2})|+1\geqslant k-1+k-3+1\geqslant
2k-3$, a contradiction.

∎

######  Claim 7.

$t(Q)\geqslant 3$.

###### Proof.

From Claim 5 and Claim 6, we have $|A|\geqslant 9$ and $|B|\geqslant 9$.
Suppose $t(Q)=2$. There is only one case:
$A=\left\\{{{c_{{i_{1}}}},{c_{{i_{2}}}},\cdots,{c_{{i_{s}}}}}\right\\}$ and
$B=\left\\{{{c_{{j_{1}}}},{c_{{j_{2}}}},\cdots,{c_{{j_{l}}}}}\right\\}$ such
that $s\geqslant 9,l\geqslant 9$ and
$\left\\{{{c_{{i_{1}}}},{c_{{i_{2}}}},\cdots,{c_{{i_{s}}}}}\right\\}\cap\left\\{{{c_{{j_{1}}}},{c_{{j_{2}}}},\cdots,{c_{{j_{l}}}}}\right\\}=\emptyset$.

There is at least one segment of $C[c_{j_{l}},c_{i_{1}}]$ and
$C[c_{i_{s}},c_{j_{1}}]$ which does not contain $w_{1},w_{2}$. Without loss of
generality, let $w_{1},w_{2}\notin C[c_{j_{l}},c_{i_{1}}]$, then there exists
some ${c_{z}}\in{A^{+}}$ satisfying
${N_{C}}({c_{z}})\cap\left[{H\cup\left\\{{{w_{1}},{w_{2}},{c_{z}}},c_{j_{l+1}},c_{j_{l+2}},\cdots,c_{j_{l+g}}\right\\}}\right]=\emptyset$.
And for any $C[c_{j_{f}},c_{j_{f+1}}]$ such that
$C[c_{j_{f}},c_{j_{f+1}}]\cap\\{w_{1},w_{2}\\}=\emptyset$, $f=1,2,\cdots,l-1$,
we have ${N_{C}}({c_{z}})\cap\\{c_{j_{f}+1},c_{j_{f}+2}\\}=\emptyset$. This
implies

${d_{G_{1}}}({c_{z}})\leqslant 3k-4-\left[{h+g+2(l-1-2)+3}\right]\leqslant
3k-1-2(g+l)\leqslant k-3,$

a contradiction(note that $g+l\geqslant k+1$).

∎

In fact, we have $t(Q)\geqslant 4$. Otherwise, suppose $t(Q)=3$, We only have
to consider one case: $A\cap B=\\{c_{m}\\}$,
$A\setminus\\{c_{m}\\}=\left\\{{{c_{{i_{1}}}},{c_{{i_{2}}}},\cdots,{c_{{i_{s}}}}}\right\\}$
and
$B\setminus\\{c_{m}\\}=\left\\{{{c_{{j_{1}}}},{c_{{j_{2}}}},\cdots,{c_{{j_{l}}}}}\right\\}$
such that $s\geqslant 8,l\geqslant 8$ and
$\left\\{{{c_{{i_{1}}}},{c_{{i_{2}}}},\cdots,{c_{{i_{s}}}}}\right\\}\cap\left\\{{{c_{{j_{1}}}},{c_{{j_{2}}}},\cdots,{c_{{j_{l}}}}}\right\\}=\emptyset$.
It is worth noting that in this case, $g+l\geqslant k$. By a similar proof as
in Claim 7, we have that there exists some ${c_{z}}\in{A^{+}}$ or
${c_{z}}\in{B^{+}}$ such that ${d_{G_{1}}}({c_{z}})\leqslant
3k-4-\left[{h+g+2(l-1-2)+3}\right]\leqslant 3k-1-2(g+l)\leqslant k-1$, a
contradiction. Since ${N_{C}}(\\{q_{1},\ q_{g}\\})\cup({N_{C}}(\\{q_{1},\
q_{g}\\}))^{+}\cup H\subseteq V(G_{1})$, we have

$\begin{array}[]{l}n_{1}\geqslant\left|C\right|+\left|H\right|\\\ \ \ \ \
\geqslant\left|H\right|+2|{N_{C}}(\\{q_{1},\ q_{g}\\})|+(t(Q)-2)(g-1)\\\ \ \ \
\ \geqslant h+2(k-g+1)+(t(Q)-2)(g-1)\\\ \ \ \ \ \geqslant
3k+1+(t(Q)-4)(g-1).\end{array}$

Because of $n_{1}\leqslant 3k-4$, we have $-5\geqslant(t(Q)-4)(g-1)$, a
contradiction to $t(Q)\geqslant 4$ and $g\geqslant 2$.

$\bf Case\ 3.$ $h\geqslant 2k-6$.

Since $G_{1}$ is a 3-connected graph and $\\{u,v,z\\}$ is not a cut-set, there
exists a vertex $x{{}^{\prime}}\in{N_{C}}(H)$, such that
$x^{{}^{\prime}-}\notin\\{w_{1},w_{2}\\}$. It is clear that
${N_{G_{1}}}({x^{{}^{\prime}-}})\cap{H}=\emptyset$, and at least two of
$\\{v,w_{1},w_{2}\\}$ cannot be adjacent to $x^{{}^{\prime}-}$. It follows
that

$d_{G_{1}}(x^{{}^{\prime}-})\leqslant 3k-4-(2k-6)-2-1=k-1,$

a contradiction.

Thus, we complete the proof of Theorem 7.

##  5 Conclusion

In this paper, we characterize a class of graphs that illustrate the sharpness
of the bound $2k$ in Theorem 4. By excluding these particular graphs, we are
able to enhance the result and establish that the bound is in fact $2k+1$ for
2-connected, $k$-regular graphs and $3k-6$ for 3-connected, $k$-regular
graphs. The problem of regular 3-connected $2$-path Hamiltonian graphs with
$n$ vertices remains intriguing whenever $3k-5\leqslant n\leqslant 3k-1$.
Naturally, we may inquire whether any interesting properties can be observed
in regular $m$-connected graphs for $m\geqslant 4$? The resolution of the
aforementioned question is necessarily relevant to the study of the
Hamiltonicity and edge-Hamiltonicity of regular graphs. However, it should be
noted that the existence of an $L$-graph (as illustrated in [11]) presents a
counterexample, showcasing higher connectivity that prevents the realization
of edge-Hamiltonicity in regular graphs. As a result, we establish $3k-1$ as
an upper bound for achieving the optimum outcome.

## References

  * [1] J.A. Bondy, U.S.R. Murty, Graph theory with applications, Macmillan, London, 1976.
  * [2] B. Bollobás, A.M. Hobbs, Hamiltonian cycles in regular graphs, in: Advances in Graph Theory, North Holland, Amsterdam, 1978.
  * [3] J.A. Bondy, M. Kouider, Hamilton cycles in regular 2-connected graphs, Journal of Combinatorial Theory. Series B 44 (1988) 177–186.
  * [4] P. Erdös, A.M. Hobbs, Hamiltonian cycles in regular graphs of moderate degree, Journal of Combinatorial Theory. Series B 23 (1977) 139–142.
  * [5] R. Häggkvist, Unsolved problems, in: Proceedings of the Fifth Hungarian Colloquim on Combinatorics, 1976.
  * [6] B. Jackson, Hamilton cycles in regular 2-connected graphs, J. Combin. Theory, Ser. B 29 (1980) 27–46.
  * [7] B. Jackson, H. Li, Y. Zhu, Dominating cycles in regular 3-connected graphs, Discrete Mathematics 102 (1991) 163–176.
  * [8] H. V. Kronk, A note on $k$-path Hamiltonian graphs, Journal of Combinatorial Theory 7 (1969) 104–106.
  * [9] D. Kühn, A. Lo, D. Osthus, K. Staden, Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs, Journal of Combinatorial Theory. Series B 121 (2016) 85–145.
  * [10] H. Li, Hamiltonian cycles and circumferences in graphs, Ph.D. Dissertation, Institute of Systems Science, Academia Sinica 1986.
  * [11] H. Li, Edge-Hamiltonian property in regular 2-connected graphs, Discrete Mathematics 82 (1990) 25–34.
  * [12] X. Li, W. Yang, On regular 2-connected 2-path Hamiltonian graphs, Discrete Mathematics 346 (2023) 113468.
  * [13] R. McCarty, Y. Wang, X. Yu, 7-Connected graphs are 4-ordered, Journal of Combinatorial Theory. Series B 141 (2020) 115–135.
  * [14] L. Ng, M. Schultz, $k$-ordered Hamiltonian graphs, Journal of Graph Theory 24 (1) (1997) 45–57.
  * [15] D.R. Woodall, The binding number of a graph and its Anderson number, Journal of Combinatorial Theory. Series B 15 (1973) 225–255.
  * [16] Y. Zhu, Z. Liu, Z. Yu, 2-connected $k$-regular graphs on at most $3k+3$ vertices to be Hamiltonian, Journal of Systems Science and Mathematical Sciences 6 (1986) 36–49 and 136–145.