Toughness and isolated toughness conditions for $P_{\ge 3}$-factor uniform graphs

Abstract

Given a graph G and an integer $k\ge 2$. A spanning subgraph F of a graph G is said to be a $P_{\ge k}$-factor of G if each component of F is a path of order at least k. A graph G is called a $P_{\ge k}$-factor uniform graph if for any two distinct edges $e_{1}$ and $e_{2}$ of G, G admits a $P_{\ge k}$-factor including $e_{1}$ and excluding $e_{2}$. More recently, Zhou and Sun (Discret Math 343:111715, 2020) gave binding number conditions for a graph to be $P_{\ge 2}$-factor and $P_{\ge 3}$-factor uniform graphs, respectively. In this paper, we present toughness and isolated toughness conditions for a graph to be a $P_{\ge 3}$-factor uniform graph, respectively.

1 Introduction

Throughout this paper we consider only simple connected graphs. For a graph $G=(V,\,E)$ with vertex set $V=V(G)$ and edge set $E=E(G)$, the degree of a vertex v in G, denoted by $d_{G}(v)$, is the number of edges incident with v. The open neighborhood of a vertex v, denoted by $N_{G}(v)$, is the set of vertices adjacent to v in G. For a subset $S\subseteq V(G)$, we use $N_{G}(S)$ to denote $\bigcup \limits _{v\in S}N_{G}(v)$. If $d_{G}(v)=0$ for some vertex v in G, then v is said to be an isolated vertex in G. If $d_{G}(v)=1$ for some vertex v in G, then v is said to be a leaf in G. Let ISO(G) be the set of isolated vertices of G, and let $i(G)=|ISO(G)|$. For $S\subseteq V(G)$, let G[S] be the subgraph of G induced by S, and write $G -S = G[V(G) \setminus S]$. For an edge subset $E_{0}$ of G, let $G-E_{0}$ be the subgraph of G obtained by deleting all edges in $E_{0}$. The number of connected components of G is denoted by $\omega (G)$.

We first introduce three parameters for a graph, namely, the binding number, the toughness and the isolated toughness. Let G be a graph. The binding number of G is defined as

$$\begin{aligned} bind(G)=\min \Big \{\frac{|N_{G}(X)|}{|X|}:\emptyset \ne X\subseteq V(G), N_{G}(X)\ne V(G) \Big \}. \end{aligned}$$

The toughness of G is defined by Chvátal in [4] as

$$\begin{aligned} t(G)=\min \Big \{\frac{|X|}{\omega (G-X)}: X\subseteq V(G), \omega (G-X)\ge 2 \Big \}, \end{aligned}$$

if G is not complete; otherwise, $t(G) =+\infty$.

The isolated toughness of G is defined by Yang et al. in [7] as

$$\begin{aligned} I(G)=\min \Big \{\frac{|X|}{i(G-X)}: X\subseteq V(G), i(G-X)\ge 2 \Big \}, \end{aligned}$$

if G is not complete; otherwise, $I(G) =+\infty$.

An ${\mathcal {H}}$-factor is a spanning subgraph of a graph, whose connected components are isomorphic to graphs from the set ${\mathcal {H}}$. A path-factor is a spanning subgraph F of G such that each component of F is a path of order at least two. This concept was introduced by Akiyama and Kano [2]. A $P_{\ge k}$-factor means a path factor in which each component has order at least $k\,(k\ge 2)$. To characterize those graphs having a $P_{\ge 3}$-factor, Kaneko [5] introduced the concept of a sun. If $H-v$ has a perfect matching for each $v\in V(H)$, then H is called a factor-critical graph. Let H be a factor-critical graph with vertex set $V(H) = \{v_{1},\, v_{2},\, \cdots , v_{n}\}$. By adding new vertices $\{u_{1},\, u_{2},\, \cdots , u_{n}\}$ together with new edges $\{v_{i}u_{i}|1\le i \le n\}$ to H, we obtain a new graph, which is called a sun. According to Kaneko, $K_1$ and $K_2$ are also suns. Usually, $K_1$ and $K_2$ are called a small sun and the others are called big suns (with order at least 6). If a component of $G-X$ is isomorphic to a sun, it is called a sun component of $G-X$. Let $Sun(G-X)$ be the set of sun components of $G-X$ and $sun(G-X)$ be the number of sun components of $G-X$.

Akiyama et al. [1] provided a criterion for a graph having a $P_{\ge 2}$-factor, which reads as follows.

Theorem 1.1

([1]) A graph G admits a $P_{\ge 2}$-factor if and only if $i(G-X)\le 2|X|$ for any $X\subseteq V(G)$.

Kaneko [5] presented a criterion for a graph having a $P_{\ge 3}$-factor, which is stated as follows.

Theorem 1.2

([5]) A graph G admits a $P_{\ge 3}$-factor if and only if $sun(G-X)\le 2|X|$ for any $X\subseteq V(G)$.

Later, Kano et al. [6] gave a simple proof to Theorem 1.2. Kaneko [5] showed that a regular graph with degree greater than or equal to two has a $P_{\ge 3}$-factor. Bazgan et al. [3] proved that for a graph G, if $t(G)\ge 1$, then G contains a $P_{\ge 3}$-factor.

Later, Zhang and Zhou [8] defined a graph G to be a $P_{\ge k}$-factor covered graph if G admits a $P_{\ge k}$-factor containing e for any $e\in E(G)$. Furthermore, they gave a characterization for a graph to be a $P_{\ge 2}$-factor covered graph and $P_{\ge 3}$-factor covered graph, respectively. Their results are stated as follows.

Theorem 1.3

([10]) Let G be a connected graph. Then G is a $P_{\ge 2}$-factor covered graph if and only if

$$\begin{aligned} i(G-X)\le 2|X|-\varepsilon _{1}(X) \end{aligned}$$

for any $X\subseteq V(G)$, where $\varepsilon _{1}(X)$ is defined as follows:

$$\begin{aligned} \varepsilon _{1}(X)= & {} \left\{ \begin{array}{lc} 2, &{} \text{ if } X \text{ is } \text{ not } \text{ an } \text{ independent } \text{ set; } \\ 1,&{} \text{ if } X \text{ is } \text{ a } \text{ nonempty } \text{ independent } \text{ set }\\ &{} \text{ and } G-X \text{ admits } \text{ a } \text{ nontrivial } \text{ component; } \\ 0,&{}\qquad \qquad \qquad \qquad \qquad \qquad \qquad \text{ otherwise. } \end{array}\right. \end{aligned}$$

Theorem 1.4

([10]) Let G be a connected graph. Then G is a $P_{\ge 3}$-factor covered graph if and only if

$$\begin{aligned} sun(G-X)\le 2|X|-\varepsilon _{2}(X) \end{aligned}$$

for any $X\subseteq V(G)$, where $\varepsilon _{2}(X)$ is defined as follows:

$$\begin{aligned} \varepsilon _{2}(X)= \left\{ \begin{array}{lr} 2,&{} \text{ if } X\ne \emptyset \text{ and } X \text{ is } \text{ not } \text{ an } \text{ independent } \text{ set; } \\ 1,&{} \text{ if } X\ne \emptyset \text{ and } X \text{ is } \text{ a } \text{ nonempty } \text{ independent } \text{ set }\\ &{}\text{ and } G-X \text{ admits } \text{ a } \text{ non-sum } \text{ component; }\\ 0,&{} \text{ otherwise. } \end{array}\right. \end{aligned}$$

Zhou et al. [9] showed that if $t(G)>\frac{2}{3}$ holds for a graph G, then G is a $P_{\ge 3}$-factor covered graph. This result improved the result of Bazgan et al. [3].

More recently, Zhou and Sun [10] defined a graph G to be a $P_{\ge k}$-factor uniform graph if for any two distinct edges $e_{1}$ and $e_{2}$ of G, G admits a $P_{\ge k}$-factor including $e_{1}$ and excluding $e_{2}$. In the same paper, they gave binding number conditions for a graph to be $P_{\ge 2}$-factor and $P_{\ge 3}$-factor uniform graphs, respectively. Their results are stated as follows.

Theorem 1.5

([10]) Let G be a 2-edge-connected graph. If $bind(G)>\frac{4}{3}$, then G is a $P_{\ge 2}$-factor uniform graph.

Theorem 1.6

([10]) Let G be a 2-edge-connected graph. If $bind(G)>\frac{9}{4}$, then G is a $P_{\ge 3}$-factor uniform graph.

In this paper, we present toughness and isolated toughness conditions for a graph to be a $P_{\ge 3}$-factor uniform graph, respectively. Our results are as follows.

Theorem 1.7

Let G be a 2-edge-connected graph. If $t(G)>1$, then G is a $P_{\ge 3}$-factor uniform graph.

Theorem 1.8

Let G be a 2-edge-connected graph. If $I(G)>2$, then G is a $P_{\ge 3}$-factor uniform graph.

We postpone the proofs of Theorems 1.7 and 1.8 to the subsequent two sections.

Fig. 1

The graph G with $t(G)=1$ (left); The edge $e_{1}$ is an edge to be excluded from G and $e_{2}$ is an edge not containing in any $P_{\ge 3}$-factor of $G^{'}=G-e_{1}$ (right)

2 The proof of Theorem 1.7

Remark 2.1

We say that the condition that $t(G)>1$ in Theorem 1.7 can not be replaced by $t(G)\ge 1$. To see this, we let G be the graph as shown in Fig. 1. Clearly, $t(G)=1$. Set $X=\{x,\,y\}$ and $G^{'}=G-e_{1}$. Then $\varepsilon _{2}(X)=2$ and $sun(G^{'}-X)=3>2=2|X|-2=2|X|-\varepsilon _{2}(X)$. By Theorem 1.4, $G^{'}$ is not a $P_{\ge 3}$-factor covered graph. So, G is not a $P_{\ge 3}$-factor uniform graph. In fact, the edge $e_{2}$ is not included into any $P_{\ge 3}$-factor of $G^{'}$.

The proof of Theorem 1.7

Proof

If G is a complete graph, then G is evidently a $P_{\ge 3}$-factor uniform graph. So, we may assume that G is not a complete graph. Since G is a 2-edge-connected graph, we have $|V (G)|\ge 4$.

We proceed by contradiction. Suppose that there exists an edge $e=uv$ in G such that $G^{'}=G-e$ is not a $P_{\ge 3}$-factor covered graph. By Theorem 1.4, there exists a vertex subset X of $V(G^{'})$ such that

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|-\varepsilon _{2}(X)+1. \end{aligned}$$

(1)

We distinguish between the following three cases.

Case 1. $|X|=0$.

In this case, we have $\varepsilon _{2}(X)=0$. By (1), we have $sun(G^{'}-X)\ge 1$. Since $G^{'}$ is connected, we have $sun(G^{'}-X)\le \omega (G^{'}-X)=\omega (G^{'})=1$. So, $sun(G^{'}-X)=1$.

By our assumption that $|V (G^{'})|=|V (G)|\ge 4$ and the definition of sun, it is easy to see that $G^{'}$ is a big sun with at least six vertices. Also, $G^{'}$ has $\frac{|V(G)|}{2}(\ge 3)$ leaves. So, G has at least one leaf. It is a contradiction to our assumption that G is a 2-edge-connected graph.

Case 2. $|X|=1$.

In this case, we have $\varepsilon _{2}(X)\le 1$. By (1), we have

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|=2. \end{aligned}$$

(2)

Since $\omega (G^{'}-X)\le \omega (G-X)+1$ and $\omega (G^{'}-X)\ge sun(G^{'}-X)$, by (2) and the definition of toughness, we have

$$\begin{aligned} 1<t(G)\le & {} \frac{|X|}{\omega (G-X)}\\\le & {} \frac{|X|}{\omega (G^{'}-X)-1}\\\le & {} \frac{|X|}{sun(G^{'}-X)-1}\\\le & {} \frac{|X|}{2|X|-1}\\= & {} 1, \end{aligned}$$

a contradiction.

Case 3. $|X|\ge 2$.

In this case, we have $\varepsilon _{2}(X)\le 2$. Also, by (1), we have

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|-1. \end{aligned}$$

(3)

Since $\omega (G-X)\ge \omega (G^{'}-X)-1$ and $\omega (G^{'}-X)\ge sun(G^{'}-X),$ by (3) and the definition of toughness, we have

$$\begin{aligned} 1<t(G)\le & {} \frac{|X|}{\omega (G-X)}\\\le & {} \frac{|X|}{\omega (G^{'}-X)-1}\\\le & {} \frac{|X|}{sun (G^{'}-X)-1}\\\le & {} \frac{|X|}{2(|X|-1)}, \end{aligned}$$

which gives $|X|<2$, a contradiction.

This completes the proof. $\square$

Fig. 2

The graph G with $I(G)=2$ (left); The edge $e_{1}$ is an edge to be excluded from G and $e_{2}$ is an edge not containing in any $P_{\ge 3}$-factor of $G^{'}=G-e_{1}$ (right)

3 The proof of Theorem 1.8

Remark 3.1

We say that the condition that $I(G)>2$ in Theorem 1.8 can not be replaced by $I(G)\ge 2$. To see this, we let G be the graph as shown in Fig. 2. Clearly, $I(G)=2$. Set $X=\{x,\,y\}$ and $G^{'}=G-e_{1}$. Then $\varepsilon _{2}(X)=2$ and $sun(G^{'}-X)=3>2=2|X|-\varepsilon _{2}(X)$. By Theorem 1.4, $G^{'}$ is not a $P_{\ge 3}$-factor covered graph. So, G is not a $P_{\ge 3}$-factor uniform graph. In fact, the edge $e_{2}$ is not contained in any $P_{\ge 3}$-factor of $G^{'}$.

The proof of Theorem 1.8

Proof

Since G is a 2-edge-connected graph, we have $|V(G)|\ge 3$. If G is the complete graph, then G is obviously a $P_{\ge 3}$-factor uniform graph. Now, we suppose that G is not the complete graph. So, $|V(G)|\ge 4$.

We proceed by contradiction. Suppose that there exists an edge $e=uv$ in G such that $G^{'}=G-e$ is not a $P_{\ge 3}$-factor covered graph. By Theorem 1.4, there exists a vertex subset X of $V(G^{'})$ such that

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|-\varepsilon _{2}(X)+1. \end{aligned}$$

(4)

We suppose that there exist a $K_{1}'s$, b $K_{2}'s$, and c big sun components $L_{1},\,\ldots ,\,L_{c}$ with $|V(L_{i})|\ge 6$ in $G^{'}-X$ for each $i=1,\,\ldots ,\,c$. By the definition of sun, we have

$$\begin{aligned} sun(G^{'}-X)=a+b+c. \end{aligned}$$

(5)

We consider the following three cases.

Case 1. $|X|=0$.

In this case, we have $\varepsilon _{2}(X)=0$. By (4), we have $sun(G^{'}-X)\ge 1$. Since G is 2-edge-connected, $G^{'}-X=G^{'}$ is connected, and then $sun(G^{'}-X)\le \omega (G^{'}-X)=\omega (G^{'})=1$. So, $sun(G^{'}-X)=1$.

By the fact that $|V (G^{'})|=|V (G)|\ge 4$ and the definition of sun, we conclude that $G^{'}$ is a big sun. Thus, $|V (G^{'})|=|V (G)|\ge 6$. Denote by N the factor-critical subgraph of $G^{'}$. According to the definition of factor-critical subgraph, we have $|V(N)|\ge 3$. So, $G^{'}$ has |V(N)| leaves. Note that $G^{'}=G-e$. Now, G must have at least $|V(N)|-2 \,(\ge 1)$ leaf. It is a contradiction to the fact G is a 2-edge-connected graph.

Case 2. $|X|=1$.

In this case, we have $\varepsilon _{2}(X)\le 1$. So, by (4), we have

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|. \end{aligned}$$

(6)

First, we assume that $c\ge 1$. We consider any one big sun component, say $L_{1}$, in $G^{'}$ and let $N_{1}$ be its factor-critical subgraph. Set $Z=V(N_{1})$, by the definition of big sun and factor-critical subgraph, we have $|Z|\ge 3$. Then, $L_{1}$ has at least three leaves in $G^{'}-X$. So, we can always choose one vertex, say w, in Z such that $G-(X\cup \{w\})$ has an isolated vertex, no matter whether u and v belong to $L_{1}$ or not. This means that $i\Big (G-(X\cup \{w\})\Big )\ge 1$.

By the definition of isolated toughness, we have

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup \{w\}|}{i\Big (G-(X\cup \{w\})\Big )}\\= & {} 2, \end{aligned}$$

a contradiction.

Second, we assume that $c=0$. We first assume that $a\ne 0$. In this case, we claim that $u\in ISO(G^{'}-X)$ or $v\in ISO(G^{'}-X)$. To see this, we first show that $X\ne \{u\}$ and $X\ne \{v\}$. Suppose, to the contrary, that $X=\{u\}$. Then $v\not \in IOS(G^{'}-X)$. Otherwise, $d_{G}(v)=1$, a contradiction to the fact that G is a 2-edge-connected graph. Also, for any other vertex $w\in V(G)\setminus \{u,\,v\}$, $w\not \in IOS(G^{'}-X)$. Otherwise, $d_{G}(w)=1$, a contradiction. So, $u \in V(G)\setminus X$ and $v \in V(G)\setminus X$. Now, let z be a vertex in $V(G)\setminus \{u,\,v\}$ such that $X=\{z\}$. Then, for any one vertex w in $V(G)\setminus \{u,\,v,\,z\}$, w can not be an isolated vertex in $G^{'}-X$, for otherwise, $d_{G}(w)=1$, a contradiction to the fact that G is a 2-edge-connected. Since $a\ge 1$, we must have $|\{u,\,v\}\cap IOS(G^{'}-X)|\ge 1$. Assume that $v\in IOS(G^{'}-X)$. Then $d_{G}(v)=2$.

Let $S=X\cup \{u\}$. Then v is an isolated vertex in $G-S$ and $|S|=2$. So,

$$\begin{aligned} 2<I(G)\le & {} \frac{|S|}{i(G-S)}\\= & {} 2, \end{aligned}$$

a contradiction.

Now, we assume that $a=0$ and $c=0$. Then, by (5) and (6), we have $b=sun(G^{'}-X)\ge 2|X|=2$. Let W be the vertex set composed of all 2b end-vertices of b $K_{2}^{'}s$, and let $T=V(G^{'})\setminus (X\cup W)$. Then we have

• $X=\{u\}$ and $v\in W\cup T$ (or $X=\{v\}$ and $u\in W\cup T$), or

• $u\in W$ and $v\in W$, or

• $u\in W$ and $v\in T$ (or $v\in W$ and $u\in T$), or

• $u\in T$ and $v\in T$.

First, we assume that $X=\{u\}$ and $v\in W\cup T$ (or $X=\{v\}$ and $u\in W\cup T$). If $X=\{u\}$ and $v\in W$, there is an independent edge vx in $G^{'}-X$. So, x is an isolated vertex in $G-\{u,\,v\}$. Then

$$\begin{aligned} 2<I(G)\le & {} \frac{|\{u,\,v\}|}{i(G-\{u,\,v\})}\\= & {} 2, \end{aligned}$$

a contradiction. If $X=\{u\}$ and $v\in T$, there is an independent edge yz in $G^{'}-X$. So, z is an isolated vertex in $G-\{u,\,y\}$. Then

$$\begin{aligned} 2<I(G)\le & {} \frac{|\{u,\,y\}|}{i(G-\{u,\,y\})}\\= & {} 2, \end{aligned}$$

a contradiction.

Second, we assume that $u\in W$ and $v\in W$.

Since $b\ge 2$, we let us and vt be two $K_{2}^{'}s$ in W of $G^{'}$. Let $S=X\cup \{u,\,v\}$. Then s and t are isolated vertices in $G-S$. Moreover, $|S|=3$. Hence,

$$\begin{aligned} 2<I(G)\le & {} \frac{|S|}{i(G-S)}\\= & {} \frac{3}{2}, \end{aligned}$$

a contradiction.

Third, we assume that $u\in W$ and $v\in T$ (or $v\in W$ and $u\in T$).

Note that $v\in T$. Since $b\ge 2$, there must exist a $K_{2}$ edge, say xy, in $G^{'}-X$ such that $x\ne u$ and $y\ne u$. Let $S=X\cup \{x\}$. Then $|S|=2$ and $G-S$ has an isolated vertex y. Therefore,

$$\begin{aligned} 2<I(G)\le & {} \frac{|S|}{i(G-S)}\\= & {} 2, \end{aligned}$$

a contradiction.

Finally, we assume that $u\in T$ and $v\in T$.

Let xy be any one $K_{2}$ edge in $G^{'}-X$. Set $S=X\cup \{x\}$. Then $|S|=2$ and $G-S$ has an isolated vertex y. Therefore,

$$\begin{aligned} 2<I(G)\le & {} \frac{|S|}{i(G-S)}\\= & {} 2, \end{aligned}$$

a contradiction.

Case 3. $|X|\ge 2$.

In this case, we have $\varepsilon _{2}(X)\le 2$. Hence, by (4), we have

$$\begin{aligned} sun(G^{'}-X)\ge 2|X|-1. \end{aligned}$$

(7)

We consider the following two subcases.

Subcase 3.1. $|X|\le a+b$.

Note that $i(G-X)\le i(G^{'}-X)\le i(G-X)+2$. We further consider the following three subcases.

Subcase 3.1.1. $i(G^{'}-X)=i(G-X)$.

In this subcase, we have $u\not \in \textit{ISO}(G^{'}-X)$ and $v\not \in ISO(G^{'}-X)$. Otherwise, $i(G^{'}-X)>i(G-X)$, a contradiction.

Let W be the vertex subset composed of all 2b end-vertices of b independent edges in $G^{'}-X$. We choose the vertex subset Y by the following procedure.

If $u\in W$ and $v\in W$, then u and v belong to two distinct $K_{2}^{'}s$ in $G^{'}-X$, and we let Y be a b-element vertex subset by choosing one vertex from each of b $K_{2}^{'}s$ such that $u\in Y$ or $v\in Y$; if one vertex of u and v, say u, is an element in W, and $v\in V(G)\setminus (X\cup ISO(G^{'}-X)\cup W)$, then we let Y be a b-element vertex subset by choosing one vertex from each of b $K_{2}^{'}s$ such that $u\in Y$; Otherwise, we let Y be a b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$.

Thus, $G-(X\cup Y)$ has $a+b$ isolated vertices, that is, $i(G-(X\cup Y))=a+b$.

Since $|X\cup Y|=|X|+b$, by the definition of isolated toughness, we have

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y|}{i\Big (G-(X\cup Y)\Big )}\\= & {} \frac{|X|+b}{a+b}\\\le & {} \frac{a+2b}{a+b}, \end{aligned}$$

resulting in $a<0$, which is impossible.

Subcase 3.1.2. $i(G^{'}-X)=i(G-X)+1$.

In this subcase, we have $u\in \textit{ISO}(G^{'}-X)$ and $v\not \in ISO(G^{'}-X)$, or $u\not \in ISO(G^{'}-X)$ and $v\in ISO(G^{'}-X)$. Suppose without loss of generality that $u\in ISO(G^{'}-X)$ and $v\not \in ISO(G^{'}-X)$. Then, $v\not \in X$, for otherwise, $i(G^{'}-X)=i(G-X)$, a contradiction to our assumption.

Let W be the same vertex subset defined as in Subcase 3.1.1. If $v\in W$, we let Y be a b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$ such that $v\in Y$. Then u is also an isolated vertex in $G-(X\cup Y)$. Thus, $i(G-(X\cup Y))=a+b$ and $|X\cup Y|=|X|+b$. Similar to Subcase 3.1.1, we obtain a contradiction.

If $v\in V(G^{'})\setminus (X\cup W\cup ISO(G^{'}-X))$, then we choose Y to be a b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$. By our choice of Y, u is still an isolated vertex in $G-(X\cup Y\cup \{v\})$. Thus, $i(G-(X\cup Y\cup \{v\}))\ge a+b$. Also, we have $|X\cup Y\cup \{v\}|=|X|+b+1$. Therefore, we obtain

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y\cup \{v\}|}{i\Big (G-(X\cup Y\cup \{v\})\Big )}\\\le & {} \frac{|X|+b+1}{a+b}\\\le & {} \frac{a+2b+1}{a+b}, \end{aligned}$$

yielding that $a<1$, which is a contradiction to our assumption that $u\in IOS(G^{'}-X)$.

Subcase 3.1.3. $i(G^{'}-X)=i(G-X)+2$.

In this subcase, we must have $\{u,\,v\}\subseteq ISO(G^{'}-X)$. So, $a=i(G^{'}-X)\ge 2$.

First, we assume that $a\ge 3$. Let Y be a b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$. Then v is also an isolated vertex in $G-(X\cup Y\cup \{u\})$. Therefore, $G-(X\cup Y\cup \{u\})$ has $a+b-1$ isolated vertices. Then

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y\cup \{u\}|}{i\Big (G-(X\cup Y\cup \{u\})\Big )}\\= & {} \frac{|X|+b+1}{a+b-1}\\\le & {} \frac{a+2b+1}{a+b-1}, \end{aligned}$$

resulting in $a<3$, which is a contradiction to our assumption.

Now, we assume that $a=2$.

First, we suppose that $c=0$. Since $b+2=a+b+c=sun(G^{'}-X)\ge 2|X|-1$ by (5) and (7), we have $b\ge 2|X|-3$. Let Y be the b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$. It is easy to see that neither u nor v is an isolated vertex in $G-(X\cup Y)$. So,

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y|}{i\Big (G-(X\cup Y)\Big )}\\= & {} \frac{|X|+b}{a+b-2}\\= & {} \frac{|X|+b}{b}, \end{aligned}$$

resulting in $b<|X|$. Thus, we have $|X|>2|X|-3$, that is, $|X|<3$. By our assumption that $|X|\ge 2$, we have $|X|=2$. So, $b=1$. Let w be one end-vertex of the unique $K_{2}$ in $G^{'}-X$. Note that $a=2$, $b=1$, $c=0$ and $|X|=2$. Then $G-(X\cup \{u,\,w\})$ has two isolated vertices, and thus

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup \{u,\,w\}|}{i\Big (G-(X\cup \{u,\,w\})\Big )}\\= & {} 2, \end{aligned}$$

a contradiction.

Second, we suppose that $c\ge 1$. For each $i=1,\,\ldots ,\,c$, we let $N_{i}$ be the factor-critical subgraph of big sun component $L_{i}$. According to the definition of big sun and factor-critical subgraph, for each $i=1,\,\ldots ,\,c$, we have $|V(N_{i})|\ge 3$. For each $i=1,\,\ldots ,\,c$, we let $Z_{i}=V(N_{i})$. So, for each $i=1,\,\ldots ,\,c$, $L_{i}-Z_{i}\cong |V(N_{i})|K_{1}$. Let $Z=Z_{1}\cup Z_{2}\cup \cdots \cup Z_{c}$. Let Y be the b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$. Since $a=2$, both u and v are not isolated vertices in $G-(X\cup Y\cup Z)$, then $G-(X\cup Y\cup Z)$ has $b+\sum \nolimits _{i=1}^{c}|V(N_{i})|$ isolated vertices. Hence,

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y\cup Z|}{i\Big (G-(X\cup Y\cup Z)\Big )} \\= & {} \frac{|X|+b+\sum \nolimits _{i=1}^{c}|V(N_{i})|}{b+\sum \nolimits _{i=1}^{c}|V(N_{i})|}, \end{aligned}$$

from which it follows that

$$\begin{aligned} |X|>b+\sum \limits _{i=1}^{c}|V(N_{i})|\ge b+3c. \end{aligned}$$

So, $2+b+c=a+b+c=sun(G^{'}-X)\ge 2|X|-1>2b+6c-1$, that is, $b+5c<3$, a contradiction to our assumption that $c\ge 1$.

Subcase 3.2. $|X|> a+b$.

In this case, we have $a+b\le |X|-1$. Since $a+b+c\ge 2|X|-1$, we must have $|c|\ge |X|$.

For each $i=1,\,\ldots ,\,c$, we let $N_{i}$ be the factor-critical subgraph of $L_{i}$. According to the definition of factor-critical subgraph, we have $|V(N_{i})|\ge 3$ for each $i=1,\,\ldots ,\,c$. For each $i=1,\,\ldots ,\,c$, we let $Z_{i}=V(N_{i})$. So, for each $i=1,\,\ldots ,\,c$, $L_{i}-Z_{i}\cong |V(N_{i})|K_{1}$. Let $Z=Z_{1}\cup Z_{2}\cup \cdots \cup Z_{c}$. Also, we let Y be the b-element vertex subset obtained by taking one vertex from each of b $K_{2}^{'}s$.

By above analysis, we have

$$\begin{aligned} i\Big (G^{'}-(X\cup Y\cup Z)\Big )= & {} a+b+\sum \limits _{i=1}^{c}|V(N_{i})|. \end{aligned}$$

(8)

Also, we have

$$\begin{aligned} |X\cup Y\cup Z|= & {} |X|+b+\sum \limits _{i=1}^{c}|V(N_{i})|. \end{aligned}$$

(9)

Since

$$\begin{aligned} i\Big (G-(X\cup Y\cup Z)\Big )\ge i\Big (G^{'}-(X\cup Y\cup Z)\Big )-2, \end{aligned}$$

by (8), (9) and the definition of isolated toughness, we have

$$\begin{aligned} 2<I(G)\le & {} \frac{|X\cup Y\cup Z|}{i\Big (G-(X\cup Y\cup Z)\Big )}\nonumber \\\le & {} \frac{|X\cup Y\cup Z|}{i\Big (G^{'}-(X\cup Y\cup Z)\Big )-2}\nonumber \\= & {} \frac{|X|+b+ \sum \limits _{i=1}^{c}|V(N_{i})|}{a+b+ \sum \limits _{i=1}^{c}|V(N_{i})|-2}. \end{aligned}$$

(10)

By (10) and $|V(N_{i})|\ge 3$ for each $i=1,\,\ldots ,\,c$, we arrive at

$$\begin{aligned} |X|>2a+b+\sum \limits _{i=1}^{c}|V(N_{i})|-4\ge 2a+b+3c-4. \end{aligned}$$

(11)

By (5) and (7), we have $a+b+c =sun(G^{'}-X)\ge 2|X|-1$. This, in joint with (11), gives $a+b+c >4a+2b+6c-9$, that is, $3a+b+5c<9$.

But, by our assumption that $|c|\ge |X|$ and $|X|\ge 2$, we have $10\le 5|X|\le 5c\le 3a+b+5c<9$, a contradiction.

This completes the proof. $\square$