Wei Gao
School of Mathematics, Hohai University, Nanjing, China.
DOI: 10.4236/jamp.2025.132017   PDF    HTML   XML   117 Downloads   470 Views   Citations

Abstract

As an appendix of [Gao et al. Sharp isolated toughness bound for fractional $\left(k,m\right)$ -deleted graphs, Acta Mathematicae Applicatae Sinica, English Series, 2025, 41(1): 252-269], the detailed proof of Theorem 4.1 in this work is presented.

Keywords

Graph, Isolated Toughness Variant, Fractional -Deleted Graph

Share and Cite:

1. Introduction

Let $k\in \mathbb{N}$ and $h:E\left(G\right)\to \left[0,1\right]$ be an indicator function defined on the edge set. A fractional $k$ -factor is a spanning subgraph induced by $E_h=\left\{e\in E\left(G\right)|h\left(e\right)>0\right\}$ if $d_G^h\left(v\right)={\displaystyle {\sum }_{v^{\prime }\in N\left(v\right)}h\left(v{v}^{\prime }\right)}=k$ for each vertex $v$ . For $m\in \mathbb{N}$ , we say that $G$ is a fractional $\left(k,m\right)$ -deleted graph if removing any $m$ edges from $G$ , the resulting subgraph still admits a fractional $k$ -factor.

The isolated toughness variant was defined by Ma and Liu [1] to measure the vulnerability of the network, which is formalized by:

$I^{\prime }\left(G\right)=\text{min}\left\{\frac{\left|S\right|}{i\left(G-S\right)-1}|S\subset V\left(G\right),i\left(G-S\right)\ge 2\right\}$

if $G$ is a non-complete graph. Moreover, $I^{\prime }\left(G\right)=+\infty$ if $G$ is a complete graph. In [2], Gao et al. provide the tight $I^{\prime }\left(G\right)$ bound for a graph $G$ to be fractional $\left(k,m\right)$ -deleted. Theorem 4.1 in [2] revealed the isolated toughness variant bound of fractional $\left(k,m\right)$ -deleted graphs, but the detailed proof was not provided because its proof trick is similar to that of the main theorem in [2]. As an appendix of Gao et al. [2], the aim of this paper is to present the detailed proof of Theorem 4.1 in [2]. It is stated that all symbols and notations are consistent with reference [2].

2. Proof of Theorem 4.1 in [2]

If $G$ is complete, then Theorem 4.1 is obvious in light of $\delta \left(G\right)\ge k+m$ . We always assume that $G$ is not complete in the subsequent discussion. Suppose that $G$ meets all the conditions of Theorem 4.1, but is not fractional $\left(k,m\right)$ -deleted. In what follows, $k\ge 2$ and $m\ge 1$ are two positive integers, ${\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ , $l_{k,m}^L$ , $l_{k,m}^U$ and ${\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$ are denoted as the statements in proof of Theorem 1.1. Also, it is akin to the definition of ${\lfloor \cdot \rfloor }^{\text{*}}$ during the subsequent proof process.

In view of Lemma 2.2 in [3] and Lemma 2.2 in [4], there exist disjoint subsets $S$ and $T$ of $V\left(G\right)$ satisfying

$\begin{array}{l}k\left|S\right|-k\left|T\right|+{\displaystyle \sum }_{x\in T}{d}_{G-S}\left(x\right)\\ =k\left|S\right|+{\displaystyle \sum }_{x\in T}\left(d_{G-S}\left(x\right)-k\right)\\ \le {\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1\le 2m-1.\end{array}$ (1)

We select $S$ and $T$ such that $\left|T\right|$ is minimum. Thus, we immediately yield $T\ne \varnothing$ , and $d_{G-S}\left(x\right)\le k-1$ for any $x\in T$ .

Due to $T\ne \varnothing$ and $\delta \left(G\right)\ge k+m$ , we have the following observation.

Observation 1. $\left|S\right|\ge m+1$ .

Let $l$ be the number of the components of $G\left[T\right]$ which are isomorphic to $K_k$ and let $T_0=\left\{x\in V\left(G\left[T\right]\right)|d_{G-S}\left(x\right)=0\right\}$ . Let $G^{\prime }$ be the subgraph inferred from $G\left[T\right]-T_0$ by deleting those $l$ components isomorphic to $K_k$ . Let $S^{\prime }$ be a set of vertices that contains exactly $k-1$ vertices in each component of $K_k$ in $G\left[T\right]$ .

Claim 1. $\left|V\left(G^{\prime }\right)\right|>0$ .

Proof of Claim 1. If $\left|V\left(G^{\prime }\right)\right|=0$ , then from (1) and Observation 1, we obtain $m+1\le \left|S\right|\le \left|T_0\right|+l+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ since $\left|S\right|$ is an integer. We verify $\left|T_0\right|+l\ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}\ge 2$ . Hence, $i\left(G-S\cup S\text{'}\right)=\left|T_0\right|+l\ge 2$ and we discuss the following subcases.

$•$ If $l\ge l_{k,m}^U=l_{k,m}^L+1$ , then $H$ can be selected with $m$ edges in $G\left[T\right]$ . We need to compare the value of $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ and $l_{k,m}^U$ .

If $k\ge 3$ , we check that

$m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}\ge \frac{2m}{k\left(k-1\right)},$ (2)

which implies $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}\ge l_{k,m}^U$ by the definition of $l_{k,m}^U$ , and hence we use $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ as the lower bound of $\left|T_0\right|+l$ . If $k=2$ , then $l_{k,m}^U=m$ and $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}=2$ . Hence, if $k=2$ and $m=1$ or 2 then $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}\ge l_{k,m}^U$ still holds. Only when $k=2$ and $m\ge 3$ , then $l_{k,m}^U>m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ and $l_{k,m}^U$ is acted as the lower bound of $\left|T_0\right|+l$ .

Collectively, if $k=2$ and $m\ge 3$ , then

$\begin{array}{c}{I}^{″}\left(G\right)\le \frac{\left|S\cup S^{\prime }\right|}{i\left(G-S-S^{\prime }\right)-1}\le \frac{\left|T_0\right|+l+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+l\left(k-1\right)}{\left|T_0\right|+l-1}\\ \le k+\frac{k+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}{\left|T_0\right|+l-1}\le k+\frac{k+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}{l_{k,m}^U-1}\\ =2+\frac{2+m-1}{m-1}=3+\frac{2}{m-1},\end{array}$

which contradicts to $I^{\prime }\left(G\right)>3+\frac{2}{m-1}$ . For other combination of $\left(k,m\right)$ , we get:

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\right|}{i\left(G-S-S^{\prime }\right)-1}\le \frac{\left|T_0\right|+l+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+l\left(k-1\right)}{\left|T_0\right|+l-1}\\ \le k+\frac{k+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}{\left|T_0\right|+l-1}\le k+\frac{k+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},\end{array}$

which contradicts to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ .

$•$ If $l\le l_{k,m}^L$ , then the number of edges in $G\left[T\right]$ is smaller than $m$ and ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le k\left(k-1\right)l$ . We verify $\left|S\right|\le \left|T_0\right|+l+\frac{k\left(k-1\right)l}{k}-1=\left|T_0\right|+kl-1$ .

If $\left|T_0\right|\ge 1$ , then $k+m\le \left|S\right|\le \left|T_0\right|+kl-1$ , $\left|T_0\right|\ge k+m+1-kl$ and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\right|}{i\left(G-S-S^{\prime }\right)-1}\le \frac{\left|T_0\right|+lk-1+l\left(k-1\right)}{\left|T_0\right|+l-1}\\ =1+\frac{2\left(k-1\right)l}{\left|T_0\right|+l-1}\le 1+\frac{2\left(k-1\right)l}{k+m-kl+l}.\end{array}$

If $l=0$ , then $I^{\prime }\left(G\right)\le 1$ , which contradicts to the hypothesis of $I^{\prime }\left(G\right)$ . Suppose $l\ge 1$ , then

$I^{\prime }\left(G\right)\le -1+\frac{2k+2m}{k+m-\left(k-1\right)l}\le -1+\frac{2k+2m}{k+m-\left(k-1\right)l_{k,m}^L}.$

If $k=2$ , then $-1+\frac{2k+2m}{k+m-\left(k-1\right)l_{k,m}^L}=\frac{1+2m}{3}$ . Note that $\left|T_0\right|\ge k+m+1-kl\ge k+m+1-k{l}_{k,m}^L=5-m$ when $k=2$ . When $m=3$ (resp. $m=4$ ) then $I^{\prime }\left(G\right)\le \frac{1+2m}{3}=\frac{7}{3}$ (resp. $I^{\prime }\left(G\right)\le \frac{1+2m}{3}=\frac{9}{3}$ ), which contradicts to $I^{\prime }\left(G\right)>3+\frac{4}{m+1}=4$ (resp. $I^{\prime }\left(G\right)>3+\frac{4}{m}=4$ ). When $m\ge 5$ , we use $\left|T_0\right|\ge 1$ instead of $\left|T_0\right|\ge 5-m$ . Thus, we have:

$I^{\prime }\left(G\right)\le 1+\frac{2\left(k-1\right)l}{\left|T_0\right|+l-1}\le 1+\frac{2\left(k-1\right)l}{l}=2k-1=3,$

which contradicts to the hypothesis of $I^{\prime }\left(G\right)$ . For $\left(k,m\right)=\left(2,1\right)$ (resp. $\left(k,m\right)=\left(2,2\right)$ ), we have $I^{\prime }\left(G\right)\le \frac{1+2m}{3}=\frac{3}{3}$ (resp. $I^{\prime }\left(G\right)\le \frac{1+2m}{3}=\frac{5}{3}$ ), which contradicts to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}=4$ (resp. $I^{\prime }\left(G\right)>5$ ). For $k\ge 3$ , we yield:

$I^{\prime }\left(G\right)<-1+\frac{2k+2m}{k+m-\left(k-1\right)\frac{2m}{k\left(k-1\right)}}=\frac{k+m+\frac{2m}{k}}{k+m-\frac{2m}{k}},$

which contradicts to $I^{\prime }\left(G\right)>k-1+\frac{k+m}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ .

If $\left|T_0\right|=0$ , then $m+1\le \left|S\right|\le kl-1$ , and $\frac{2m}{k\left(k-1\right)}>l_{k,m}^L\ge l\ge \frac{m+2}{k}$ which reveals $k=2$ and $m\ge 3$ . Hence, $l_{k,m}^L=l_{2,m}^L=m-1$ , $l\ge \frac{m+2}{2}$ if $m$ is even, $l\ge \frac{m+3}{2}$ if $m$ is odd. Hence, if $m\ge 4$ is even, then

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\right|}{i\left(G-S-S^{\prime }\right)-1}\le \frac{lk-1+l\left(k-1\right)}{l-1}=2k-1+\frac{2k-2}{l-1}\\ \le 2k-1+\frac{2k-2}{\frac{m+2}{k}-1}=3+\frac{4}{m},\end{array}$

which contradicts to $I^{\prime }\left(G\right)>3+\frac{4}{m}$ .

If $m\ge 3$ is odd, then

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\right|}{i\left(G-S-S^{\prime }\right)-1}\le \frac{lk-1+l\left(k-1\right)}{l-1}=2k-1+\frac{2k-2}{l-1}\\ \le 2k-1+\frac{2k-2}{\frac{m+3}{k}-1}=3+\frac{4}{m+1},\end{array}$

which contradicts to $I^{\prime }\left(G\right)>3+\frac{4}{m+1}$ . $\square$

Let $G^{\prime }=G_1\cup G_2$ where $G_1$ is the union of components of $G^{\prime }$ which satisfies that $d_{G-S}\left(v\right)=k-1$ for each vertex $v\in V\left(G_1\right)$ and $G_2=G^{\prime }-G_1$ . In terms of Lemma 2.2 in [5], $G_1$ has a maximum independent set $I_1$ and the covering set $C_1=V\left(G_1\right)-I_1$ such that

$\left|V\left(G_1\right)\right|\le {\displaystyle \sum }_{i=1}^k\left(k-i+1\right)\left|I^{\left(i\right)}\right|-\frac{\left|I^{\left(1\right)}\right|}{2}\le \left(k-\frac{1}{2}\right)\left|I_1\right|,$ (3)

and

$\left|C_1\right|\le {\displaystyle \sum }_{i=1}^k\left(k-i\right)\left|I^{\left(i\right)}\right|-\frac{\left|I^{\left(1\right)}\right|}{2},$ (4)

where $I^{\left(i\right)}=\left\{v\in I_1,d_{G_1}\left(v\right)=k-i\right\}$ for $1\le i\le k$ and ${\displaystyle \sum }_{i=1}^k\left|I^{\left(i\right)}\right|=\left|I_1\right|$ . Using the definition of $G^{\prime }$ and $G_2$ , we verify that each component of $G_2$ has a vertex of degree at most $k-2$ in $G-S$ . We have the following observation by the definition of $G_2$ and $\delta \left(G\right)\ge k+m$ .

Observation 2. If $G_2\ne \varnothing$ , then $k\ge 3$ and $\left|S\right|\ge m+2$ .

Denote $I_2$ by an independent set of $G_2$ which is selected by the procedure described in Gao et al. [2]. Set $W=V\left(G\right)-S-T$ and $U=S\cup S^{\prime }\cup C_1\cup \left(N_G\left(I_1\right)\cap W\right)\cup N_{G-S}\left(I_2\right)=S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\cup N_{G-S}\left(I_2\right)$ .

The following discussion is divided into two cases by means of whether $\left|T_0\right|+l=0$ .

Case 1. $\left|T_0\right|+l\ge 1$ .

The two claims below consider two extreme cases respectively.

Claim 2. If $\left|T_0\right|+l\ge 1$ , then $\left|I_2\right|\ne 0$ .

Proof of Claim 2. Suppose $\left|I_2\right|=0$ , then $\left|I_1\right|\ne 0$ by $\left|V\left(G^{\prime }\right)\right|>0$ .

In view of (1) and (3), we obtain $\left|T\right|=\left|V\left(G_1\right)\right|+\left|T_0\right|+lk$ ,

$\begin{array}{c}k\left|S\right|\le k\left|T\right|-d_{G-S}\left(T\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\\ \le \left(k-\frac{1}{2}\right)\left|I_1\right|+k\left|T_0\right|+lk+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\end{array}$

and

$\begin{array}{c}\left|S\right|\le \left(1-\frac{1}{2k}\right)\left|I_1\right|-\frac{1}{k}+\left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\\ \le \left|I_1\right|+\left|T_0\right|+l+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}\\ \le \left|I_1\right|+\left|T_0\right|+l+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}.\end{array}$

Then, we infer:

$m+1\le \left|S\right|\le \left|I_1\right|+\left|T_0\right|+l+{\lfloor \frac{2m}{k}\rfloor }^{\text{*}},$

which implies $\left|T_0\right|+l+\left|I_1\right|\ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ . Therefore,

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\right|}{i\left(G-S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\right)-1}\\ \le \frac{\left|I_1\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+\left|T_0\right|+l+l\left(k-1\right)+\left|I_1\right|\left(k-1\right)}{\left|I_1\right|+l+\left|T_0\right|-1}\\ \le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+l+\left|T_0\right|-1}.\end{array}$

$•$ If $G\left[T\right]$ contains at least $m$ edges, then ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le 2m$ and $\left|I_1\right|+l\ge l_{k,m}^L+1=l_{k,m}^U$ . It is necessary to compare the value of $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ and $l_{k,m}^U$ , hence to determine the lower bound of $\left|T_0\right|+l+\left|I_1\right|$ . Using the same fashion in Claim 1, we know that if $k=2$ and $m\ge 3$ , then $l_{k,m}^U>m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ , and otherwise the opposite is true.

Hence, if $k\ge 3$ or $\left(k,m\right)=\left(2,1\right)$ or $\left(k,m\right)=\left(2,2\right)$ , then

$I^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+l+\left|T_0\right|-1}\le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

which contradicts to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ . If $k=2$ and $m\ge 3$ , then

$\begin{array}{c}{I}^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+l+\left|T_0\right|-1}\\ \le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{l_{k,m}^U-1}=2+\frac{m+1}{m-1}=3+\frac{2}{m-1},\end{array}$

which contradicts to the hypothesis of $I^{\prime }\left(G\right)$ .

$•$ If $\left|E\left(G\left[T\right]\right)\right|<m$ , then ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le 2m-1$ . We get:

$I\text{'}\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+l+\left|T_0\right|-1}\le k+\frac{{\lfloor \frac{2m-1}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

a contradiction to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ if $k\ge 3$ or $\left(k,m\right)=\left(2,1\right)$ or $\left(k,m\right)=\left(2,2\right)$ .

Suppose $k=2$ and $m\ge 3$ . Then, $l\le m-1$ , $\left|T\right|=\left|I_1\right|+\left|T_0\right|+2l$ ,

$\begin{array}{c}2\left|S\right|\le 2\left|T\right|-d_{G-S}\left(T\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\\ \le \left|I_1\right|+2\left|T_0\right|+2l+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1,\end{array}$

$\left|S\right|\le \frac{\left|I_1\right|}{2}+\left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2},$

and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\right|}{i\left(G-S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\right)-1}\\ \le \frac{\frac{\left|I_1\right|}{2}+\left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2}+l+\left|I_1\right|}{\left|I_1\right|+\left|T_0\right|+l-1}\\ =2+\frac{\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2}{l+\left|I_1\right|+\left|T_0\right|-1}.\end{array}$

If $\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2<0$ , then $I^{\prime }\left(G\right)<2$ , a contradiction. Thus, $\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2\ge 0$ .

To maximize ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)$ , we first take $l$ edges from $l{K}_2$ into $H$ (each edge contributes 2 to ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)$ ), then take $\text{min}\left\{m-l,\left|I_1\right|\right\}$ edges between $I_1$ and $W$ into $H$ (each edge contributes 1 to ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)$ ), and finally randomly select $m-l-\left|I_1\right|$ edges in the rest subgraphs if $m-l-\left|I_1\right|\ge 1$ (each edge contributes zero to ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)$ ). We have:

$I^{\prime }\left(G\right)\le 2+\frac{\frac{2l+\text{min}\left\{m-l,\left|I_1\right|\right\}-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+\left|T_0\right|+l-1}.$

Suppose $\left|T_0\right|\ge 1$ . If $\text{min}\left\{m-l,\left|I_1\right|\right\}=m-l$ , then $m-l\le \left|I_1\right|$ , $\text{max}\left\{\frac{m+l-\left|I_1\right|}{2}\right\}=m-1$ and it reaches the maximum value when $l=m-1$ and $\left|I_1\right|=1$ , and hence

$\begin{array}{c}{I}^{\prime }\left(G\right)\le 2+\frac{\frac{m+l-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+\left|T_0\right|+l-1}\le 2+\frac{m-1+\frac{3}{2}-1}{\left|I_1\right|+1+l-1}\\ =2+\frac{m-\frac{1}{2}}{\left|I_1\right|+l}<2+\frac{m}{m}=3,\end{array}$

a contradiction to the hypothesis of $I^{\prime }\left(G\right)$ . If $\text{min}\left\{m-l,\left|I_1\right|\right\}=\left|I_1\right|$ , then $m-l\ge \left|I_1\right|$ and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le 2+\frac{\frac{2l+\left|I_1\right|-1}{2}-\left|T_0\right|-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+\left|T_0\right|+l-1}\\ \le 2+\frac{\frac{2l+\left|I_1\right|-1}{2}-1-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+1+l-1}\\ =2+\frac{l+\frac{1}{2}}{\left|I_1\right|+l}<2+\frac{l+1}{1+l}=3,\end{array}$

a contradiction to the hypothesis of $I^{\prime }\left(G\right)$ .

Considering $\left|T_0\right|=0$ , hence $l\ge 1$ and

$I^{\prime }\left(G\right)\le 2+\frac{\frac{2l+\text{min}\left\{m-l,\left|I_1\right|\right\}-1}{2}-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+l-1}.$

If $\text{min}\left\{m-l,\left|I_1\right|\right\}=m-l$ , then $m-l\le \left|I_1\right|$ , $\text{max}\left\{\frac{m+l-\left|I_1\right|}{2}\right\}=m-1$ and it reaches the maximum value when $l=m-1$ and $\left|I_1\right|=1$ , and hence

$I^{\prime }\left(G\right)\le 2+\frac{\frac{m+l-1}{2}-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+l-1}\le 3+\frac{3}{2\left(m-1\right)},$

a contradiction to the hypothesis of $I^{\prime }\left(G\right)$ . If $\text{min}\left\{m-l,\left|I_1\right|\right\}=\left|I_1\right|$ , then $m-l\ge \left|I_1\right|$ and

$I^{\prime }\left(G\right)\le 2+\frac{\frac{2l+\left|I_1\right|-1}{2}-\frac{1}{2}\left|I_1\right|+2}{\left|I_1\right|+l-1}.$

Since the numerator part refer to $\left|S\cup S^{\prime }\cup N_{G-S}\left(I_1\right)\right|$ which is an integer, we infer:

$I^{\prime }\left(G\right)\le 2+\frac{l+1}{\left|I_1\right|+l-1}\le 2+\frac{l+1}{1+l-1}=3+\frac{1}{l}.$

Note that when $\left|I_1\right|=1$ , according to

$\begin{array}{c}m+1\le \left|S\right|\le \frac{\left|I_1\right|}{2}+\left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{2}\\ \le \frac{1}{2}+l+\frac{2l+\text{min}\left\{m-l,\left|I_1\right|\right\}-1}{2}\\ =\frac{1}{2}+2l,\end{array}$

we have $2l\ge m+1$ (i.e. $l\ge \frac{m+1}{2}$ ). Hence $I^{\prime }\left(G\right)\le 3+\frac{1}{l}\le 3+\frac{2}{m+1}$ , a contradiction to the hypothesis of $I^{\prime }\left(G\right)$ . $\square$

Claim 3. If $\left|T_0\right|+l\ge 1$ , then $\left|I_1\right|\ne 0$ .

Proof of Claim 3. Suppose $\left|I_1\right|=0$ . We yield $\left|I_2\right|\ne 0$ by $\left|V\left(G^{\prime }\right)\right|>0$ , and hence $k\ge 3$ (thus we don’t consider the case in $k=2$ ).

Let $v_1,v_2,\cdots ,v_{\left|I_2\right|}$ be vertices in $I_2$ such that $d_{G-S}\left(v_1\right)\le k-2$ and $d_{G-S}\left(v_1\right)\le d_{G-S}\left(v_2\right)\le \cdots \le d_{G-S}\left(v_{\left|I_2\right|}\right)$ . Then $\left|T\right|=\left|V\left(G_2\right)\right|+\left|T_0\right|+lk$ ,

$\begin{array}{c}k\left|S\right|\le k\left|T\right|-d_{G-S}\left(T\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\\ \le k\left|T_0\right|+lk+{\displaystyle \sum }_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)\\ +\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\end{array}$

and

$\begin{array}{c}\left|S\right|\le \left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}.\end{array}$

We acquire $i\left(G-U\right)\ge 2$ where $U=S\cup S^{\prime }\cup N_{G-S}\left(I_2\right)$ and

$\begin{array}{c}\left|U\right|\le \left|S\right|+\left|S^{\prime }\right|+\left|N_{G-S}\left(I_2\right)\right|\\ \le \left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}+l\left(k-1\right)+{\displaystyle \sum }_{i=1}^{\left|I_2\right|}{d}_{G-S}\left(v_i\right)\\ =\left|T_0\right|+lk+{\displaystyle \sum }_{i=1}^{\left|I_2\right|}\left(-\frac{d_{G-S}^2\left(v_i\right)}{k}+\left(2-\frac{1}{k}\right)d_{G-S}\left(v_i\right)+1\right)\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}\\ \le \left|T_0\right|+lk+\left(\left|I_2\right|-1\right)\left(-\frac{{\left(k-1\right)}^2}{k}+\left(2-\frac{1}{k}\right)\left(k-1\right)+1\right)\\ +\left(-\frac{{\left(k-2\right)}^2}{k}+\left(2-\frac{1}{k}\right)\left(k-2\right)+1\right)\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}\\ =\left|T_0\right|+lk+k\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{3}{k}.\end{array}$

Hence, $\left|U\right|\le \left|T_0\right|+lk+k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$ .

It ensures that to maximize $\left|U\right|$ , only one vertex in $I_2$ has degree $k-2$ in $G-S$ , and others have degree $k-1$ in $G-S$ . Hence, $\left|S\right|$ can be re-bounded by:

$\begin{array}{c}\left|S\right|\le \left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}\\ \le \frac{\left(\left|I_2\right|-1\right)\left(\left(k-1\right)+1\right)\left(k-\left(k-1\right)\right)+\left(\left(k-2\right)+1\right)\left(k-\left(k-2\right)\right)}{k}\\ \left|T_0\right|+l+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}\\ =\left|T_0\right|+l+\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}+1-\frac{3}{k},\end{array}$

which reveals $m+2\le \left|S\right|\le \left|T_0\right|+l+\left|I_2\right|+1+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor$ and

$\left|T_0\right|+l+\left|I_2\right|\ge m+1-\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor \ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}.$

Furthermore, we get:

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|U\right|}{i\left(G-U\right)-1}\le \frac{\left|T_0\right|+lk+k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}}{\left|I_2\right|+\left|T_0\right|+l-1}\\ \le \frac{k\left(\left|T_0\right|+l+\left|I_2\right|\right)+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}}{\left|I_2\right|+\left|T_0\right|+l-1}\\ =k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_2\right|+\left|T_0\right|+l-1}\\ \le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},\end{array}$

which contradicts to the hypothesis of $I^{\prime }\left(G\right)$ . $\square$

From Claim 2 and Claim 3, we have $\left|I_1\right|\ge 1$ , $\left|I_2\right|\ge 1$ and $k\ge 3$ (hence we don’t consider the special circumstances of $k=2$ ).

Denote $v_1,v_2,\cdots ,v_{\left|I_2\right|}$ as vertices in $I_2$ as defined in Claim 3. We obtain:

$\left|T\right|=\left|V\left(G_1\right)\right|+\left|V\left(G_2\right)\right|+\left|T_0\right|+lk,$

$\begin{array}{c}k\left|S\right|\le k\left(\left|T_0\right|+l\right)+\left(k-\frac{1}{2}\right)\left|I_1\right|+{\displaystyle \sum }_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)\\ +\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\end{array}$

and

$\begin{array}{c}\left|S\right|\le \left|T_0\right|+l+\left(1-\frac{1}{2k}\right)\left|I_1\right|+\frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}.\end{array}$

We confirm that $i\left(G-U\right)\ge 3$ where $U=S\cup S^{\prime }\cup C_1\cup \left(N_G\left(I_1\right)\cap W\right)\cup N_{G-S}\left(I_2\right)$ and $\left|U\right|\le \left|T_0\right|+lk+k\left|I_1\right|+k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$ since $\left|U\right|$ is an integer.

By maximizing $\left|U\right|$ , we can see that in the extreme value setting, only one vertex in $I_2$ has degree $k-2$ in $G-S$ , and the others have degree $k-1$ in $G-S$ . Thus, $\left|S\right|$ can be re-bounded by:

$\begin{array}{c}\left|S\right|\le \frac{\left(\left|I_2\right|-1\right)\left(\left(k-1\right)+1\right)\left(k-\left(k-1\right)\right)+\left(\left(k-2\right)+1\right)\left(k-\left(k-2\right)\right)}{k}\\ \left|T_0\right|+l+\left(1-\frac{1}{2k}\right)\left|I_1\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}\\ =\left|T_0\right|+l+\left|I_1\right|+\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}+1-\frac{3}{k},\end{array}$

which reveals $m+2\le \left|S\right|\le \left|T_0\right|+l+\left|I_1\right|+\left|I_2\right|+1+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}\text{}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor$ by Observation 2. We further infer $\left|T_0\right|+l+\left|I_1\right|+\left|I_2\right|\ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ .

Therefore, we infer:

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|U\right|}{i\left(G-U\right)-1}\\ \le \frac{\left|T_0\right|+lk+k\left|I_1\right|+k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}}{\left|I_1\right|+\left|I_2\right|+\left|T_0\right|+l-1}\\ \le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+\left|I_2\right|+\left|T_0\right|+l-1}\le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},\end{array}$

a contradiction.

Case 2. $\left|T_0\right|+l=0$ .

Again, we consider two extreme cases in Claim 4 and Claim 5 respectively.

Claim 4. If $\left|T_0\right|+l=0$ , then $\left|I_2\right|\ne 0$ .

Proof of Claim 4. Suppose $\left|I_2\right|=0$ , then we infer $\left|I_1\right|\ne 0$ , $\left|T\right|=\left|V\left(G_1\right)\right|$ and $k\left|S\right|\le k\left|T\right|-d_{G-S}\left(T\right)+\left({\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\right)-1=\left|T\right|+{\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)-1$ .

If $\left|I_1\right|=1$ , then $\left|T\right|\le k-1$ and $\left|S\right|\le \frac{\left|T\right|+\left({{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1}{k}\le \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-2}{k}+1$ . Thus, $k+m\le \delta \left(G\right)\le \left|S\right|+\left(k-1\right)\le k+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-2}{k}\le k+\frac{2m-2}{k}$ , a contradiction. Hence, $\left|I_1\right|\ge 2$ .

We acquire $\left|T\right|\le \left(k-\frac{1}{2}\right)\left|I_1\right|$ , $\left|S\right|\le \frac{\left|T\right|+\left({{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1}{k}\le \left(1-\frac{1}{2k}\right)\left|I_1\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}$ , i.e. $m+1\le \left|S\right|\le \left|I_1\right|+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{k}\rfloor$ . Therefore,

$\begin{array}{l}\left|I_1\right|\ge m+1-\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{k}\rfloor \\ \ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}.\end{array}$

Set $U=S\cup C_1\cup \left(N_G\left(I_1\right)\cap W\right)$ , we have $i\left(G-U\right)=\left|I_1\right|\ge 2$ . According to (4), we yield:

$\begin{array}{c}\left|U\right|\le \left|S\right|+\left|C_1\right|+{\displaystyle \sum }_{i=1}^k\left(i-1\right)\left|I^{\left(i\right)}\right|\\ \le \left(1-\frac{1}{2k}\right)\left|I_1\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\\ -\frac{1}{k}+{\displaystyle \sum }_{i=1}^k\left(k-i\right)\left|I^{\left(i\right)}\right|-\frac{\left|I^{\left(1\right)}\right|}{2}+{\displaystyle \sum }_{i=1}^k\left(i-1\right)\left|I^{\left(i\right)}\right|\\ \le k\left|I_1\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{\left|I_1\right|}{2k}-\frac{1}{k}.\end{array}$

Hence,

$\left|U\right|\le k\left|I_1\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$

due to the integer property of $\left|U\right|$ , and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|U\right|}{i\left(G-U\right)-1}\le \frac{k\left|I_1\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}}{\left|I_1\right|-1}\\ =k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|-1}.\end{array}$

$•$ If $\left|E\left(G\left[T\right]\right)\right|\ge m$ , then ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le 2m$ and $\left|I_1\right|\ge l_{k,m}^U$ . If $k\ge 3$ or $\left(k,m\right)=\left(2,1\right)$ or $\left(k,m\right)=\left(2,2\right)$ , then $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}>l_{k,m}^U$ , hence, the lower bound of $\left|I_1\right|$ takes $m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ and

$I^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|-1}\le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

a contradiction to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ . If $k=2$ and $m\ge 3$ , then $l_{2,m}^U=m>2=m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}$ and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|-1}\\ \le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{l_{k,m}^U-1}=2+\frac{m-1+2}{m-1}=3+\frac{2}{m-1},\end{array}$

a contradiction.

$•$ If $\left|E\left(G\left[T\right]\right)\right|<m$ , then ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le 2m-1$ . If $k\ge 3$ or $\left(k,m\right)=\left(2,1\right)$ or $\left(k,m\right)=\left(2,2\right)$ , then

$I^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|-1}\le k+\frac{{\lfloor \frac{2m-1}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

a contradiction to $I^{\prime }\left(G\right)>k-1+\frac{m+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}}$ .

Suppose $k=2$ and $m\ge 3$ . Then, ${\displaystyle {\sum }_{x\in T}{d}_H\left(x\right)}-e_H\left(S,T\right)\le \text{min}\left\{m,\left|I_1\right|\right\}$ . If $\left|I_1\right|\le m$ , then

$\begin{array}{c}m+1\le \left|S\right|\le \left|I_1\right|+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{k}\rfloor \\ \le \left|I_1\right|+\lfloor \frac{\left|I_1\right|-1}{2}\rfloor \le \frac{3\left|I_1\right|}{2}-\frac{1}{2},\end{array}$

$\left|I_1\right|\ge \frac{2m}{3}+1$ , and

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup N_{G-S}\left(I_1\right)\right|}{i\left(G-S\cup N_{G-S}\left(I_1\right)\right)-1}\\ \le \frac{\frac{3\left|I_1\right|}{2}-\frac{1}{2}+\left|I_1\right|}{\left|I_1\right|-1}=\frac{5}{2}+\frac{2}{\left|I_1\right|-1}\\ \le \frac{5}{2}+\frac{2}{\frac{2}{3}m}=\frac{5}{2}+\frac{3}{m},\end{array}$

a contradiction to the hypothesis of $I^{\prime }\left(G\right)$ .

If $m<\left|I_1\right|$ , then

$\begin{array}{c}\left|S\right|\le \left|I_1\right|+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-1}{k}\rfloor \\ \le \left|I_1\right|+\lfloor \frac{m-1}{2}\rfloor \le \left|I_1\right|+\frac{m-1}{2},\end{array}$

and thus

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{\left|S\cup N_{G-S}\left(I_1\right)\right|}{i\left(G-S\cup N_{G-S}\left(I_1\right)\right)-1}\le \frac{\left|I_1\right|+\frac{m-1}{2}+\left|I_1\right|}{\left|I_1\right|-1}\\ =2+\frac{m+3}{2\left(\left|I_1\right|-1\right)}\le 2+\frac{m+3}{2\left(m+1-1\right)}=\frac{5}{2}+\frac{3}{2m},\end{array}$

a contradiction. $\square$

Claim 5. If $\left|T_0\right|+l=0$ , then $\left|I_1\right|\ne 0$ .

Proof of Claim 5. Suppose $\left|I_1\right|=0$ , then $\left|I_2\right|\ne 0$ in terms of $\left|V\left(G^{\prime }\right)\right|>0$ , and hence $k\ge 3$ .

If $\left|I_2\right|=1$ , then we set $d_{\min }=\min \left\{d_{G-S}\left(v\right)|v\in G_2\right\}$ and $z\in V\left(G_2\right)$ such that $d_{G-S}\left(z\right)=d_{\min }$ , thus $d_{\min }\in \left\{1,\cdots ,k-2\right\}$ . Hence, we deduce:

$\begin{array}{c}k\left|S\right|\le k\left|T\right|-d_{G-S}\left(T\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1\\ \le \left|T\right|\left(k-d_{\min }\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1,\end{array}$

$\begin{array}{c}\left|S\right|\le \frac{\left|T\right|\left(k-d_{\min }\right)+\left({{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1}{k}\\ \le \frac{\left(k-1\right)\left(k-d_{\min }\right)-1}{k}+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\end{array}$

and

$\begin{array}{l}k+m\le \delta \left(G\right)\le d_{\min }+\left|S\right|\\ \le d_{\min }+\frac{\left(k-1\right)\left(k-d_{\min }\right)-1}{k}+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\\ =k-1+\frac{d_{\min }}{k}-\frac{1}{k}+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\\ \le k-1+\frac{k-2}{k}-\frac{1}{k}+\frac{2m}{k}\\ =k+\frac{2m-3}{k},\end{array}$

a contradiction.

Hence, we get $\left|I_2\right|\ge 2$ . Let $v_1,v_2,\cdots ,v_{\left|I_2\right|}$ be vertices in $I_2$ as defined in Claim 3, thus $d_{G-S}\left(v_1\right)\le k-2$ and $d_{G-S}\left(v_1\right)\le d_{G-S}\left(v_2\right)\le \cdots \le d_{G-S}\left(v_{\left|I_2\right|}\right)$ . We have $\left|T\right|=\left|V\left(G_2\right)\right|$ ,

$k\left|S\right|\le {\displaystyle \sum }_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)+\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1$

and

$\left|S\right|\le \frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k}.$

In terms of $i\left(G-U\right)=\left|I_2\right|\ge 2$ where $U=S\cup N_{G-S}\left(I_2\right)$ and $\left|U\right|\le k\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{3}{k}$ which implies $\left|U\right|\le k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$ . We yield:

$\begin{array}{c}{I}^{\prime }\left(G\right)\le \frac{k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}}{\left|I_2\right|-1}\\ =k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_2\right|-1}.\end{array}$

It is clear to see that to maximize $\left|U\right|$ , only one vertex in $\left|I_2\right|$ has degree $k-2$ in $G-S$ , and others have degree $k-1$ in $G-S$ . Using the same fashion as Claim 3, $\left|S\right|$ can be formulated by:

$m+2\le \left|S\right|\le \left|I_2\right|+1+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor$

and hence

$\left|I_2\right|\ge m+1-\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor \ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}.$ (5)

Hence, we have:

$I^{\prime }\left(G\right)\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_2\right|-1}\le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

a contradiction. $\square$

From Claim 4 and Claim 5, we ensure $\left|I_1\right|\ge 1$ and $\left|I_2\right|\ge 1$ , and thus $k\ge 3$ .

Denote $v_1,v_2,\cdots ,v_{\left|I_2\right|}$ by vertices in $I_2$ as defined in Claim 3. We get $\left|T\right|=\left|V\left(G_1\right)\right|+\left|V\left(G_2\right)\right|$ ,

$\begin{array}{c}k\left|S\right|\le \left(k-\frac{1}{2}\right)\left|I_1\right|+{\displaystyle \sum }_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)\\ +\left({\displaystyle \sum }_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)\right)-1,\end{array}$

$\begin{array}{c}\left|S\right|\le \left(1-\frac{1}{2k}\right)\left|I_1\right|+\frac{{{\displaystyle \sum }}_{i=1}^{\left|I_2\right|}\left(d_{G-S}\left(v_i\right)+1\right)\left(k-d_{G-S}\left(v_i\right)\right)}{k}\\ +\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{1}{k},\end{array}$

$i\left(G-U\right)\ge 2$ where $U=S\cup C_1\cup \left(N_G\left(I_1\right)\cap W\right)\cup N_{G-S}\left(I_2\right)$ and

$\left|U\right|\le \left(k-\frac{1}{2k}\right)\left|I_1\right|+k\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}-\frac{3}{k}.$

Hence, $\left|U\right|\le k\left|I_1\right|+k\left|I_2\right|+{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}$ since $\left|U\right|$ is an integer.

By maximizing $\left|U\right|$ , we can see that in the extreme value setting, only one vertex in $I_2$ has degree $k-2$ in $G-S$ , and the others have degree $k-1$ in $G-S$ . Thus, in terms of the similar discussion in Case 1, $\left|S\right|$ can be re-bounded by:

$\left|S\right|\le \left|I_1\right|+\left|I_2\right|+\frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}+1-\frac{3}{k},$

which reveals $m+2\le \left|S\right|\le \left|I_1\right|+\left|I_2\right|+1+\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor$ and

$\left|I_1\right|+\left|I_2\right|\ge m+1-\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)-3}{k}\rfloor \ge m+1-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}.$ (6)

Collectively, we infer:

$I^{\prime }\left(G\right)\le \frac{\left|U\right|}{i\left(G-U\right)-1}\le k+\frac{{\lfloor \frac{{{\displaystyle \sum }}_{x\in T}{d}_H\left(x\right)-e_H\left(S,T\right)}{k}\rfloor }^{\text{*}}+k}{\left|I_1\right|+\left|I_2\right|-1}\le k+\frac{{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}+k}{m-{\lfloor \frac{2m}{k}\rfloor }^{\text{*}}},$

a contradiction.

In all, the proof of the desired theorem is completed. $\square$