本文只讨论有限无向简单图. 设$ G $是一个图, 其顶点集和边集分别表示为$ V(G) $和$ E(G) $. 记$ d_{G}(v) $和$ N_{G}(v) $ (简记为$ d(v) $和$ N(v) $)为图$ G $中顶点$ v $的度和邻域, $ \delta(G) $是图$ G $的最小度, $ G[S] $表示由$ S\subseteq V(G) $导出的子图. 设$ i(G) $为图$ G $中孤立点的数量, $ G_{1}\vee G_{2} $表示将每一对来自$ G_{1} $ 和$ G_{2} $的顶点通过边相连. 其他相关符号和标记可参考[1].

设$ a, b, k $为正整数满足$ 1\le a\le b $, $ h: E(G)\to[0, 1] $是定义在边集上的示性函数. 分数$ [a, b] $-因子是由边集$ E_{h}=\{e\in E(G)|h(e) > 0\} $决定的生成图, 对任意$ v\in V(G) $满足$ a\le \sum_{v'\in N(v)}h(vv')\le b $. 图$ G $存在分数$ [a, b] $-因子是指满足上述条件的示性函数$ h $存在. 若$ a=b=k $, 则分数$ [a, b] $-因子退化为分数$ k $-因子.

文献[2]引入孤立韧度的概念, 对于非完全图定义为

$ I(G)=\min\left\{\frac{|S|}{i(G-S)}\Big{|}S\subset V(G), i(G-S)\ge2\right\}, $

对于完全图则规定$ I(G)=+\infty $.

近20年来, 关于孤立韧度和分数因子的关系, 得到了丰富的结果. [3]指出图$ G $存在分数$ k $-因子若$ \delta(G)\ge k $且$ I(G)\ge k $. [4]给出了图存在分数$ [a, b] $-因子的一个孤立韧度条件, 并说明结论在一定意义下是"最好"的. 最近, [5]得到了在删除任意$ n $个顶点条件下依然存在分数$ k $-因子的孤立韧度条件, 同时说明该条件是紧的.

本文的主要贡献在于给出一个图存在分数$ [a, b] $-因子的孤立韧度条件, 并且通过反例说明该条件是最好的. 本文的组织结构如下: 首先对[4]中的结果证明, 反例及猜想进行分析; 其次, 给出分数$ [a, b] $-因子存在性的紧孤立韧度条件, 结果的最好性通过反例说明; 然后, 对本文主要结果给出详细证明.

首先, 我们对文献[4]中存在的问题进行分析. 文献[4]给出如下结论:

定理2.1^[4]  设$ G $是一个图, $ a, b $都是正整数, 且$ 2\le a < b $. 若$ G $的孤立韧度与最小度满足$ \delta(G)\ge I(G)\ge a-1+\frac{a-1}{b} $, 则$ G $有分数$ [a, b] $-因子.

作者对孤立韧度的"最好性"用下面的例子来阐述: $ a\ge2 $, $ V(G)=V(K_{n(a-1)})\cup V((nb+1)K_{1})\cup V(K_{(nb+1)(a-1)}) $. 令$ V((nb+1)K_{1})=\{v_{1}, v_{2}, \cdots, v_{nb+1}\} $, $ \{u_{1}, u_{2}, \cdots, u_{nb+1}\}\subseteq V(K_{(nb+1)(a-1)}) $. $ E(G)=E(K_{n(a-1)})\cup E(K_{(nb+1)(a-1)})\cup\{u_{i}v_{i}: i=1, \cdots, nb+1\}\cup\{xy: x\in V(K_{n(a-1)}), y\in(nb+1)K_{1}\} $.

此外, 文献[4]还给出如下猜想:

猜想2.2^[4]  定理1.1对$ a=b $也成立. 即当整数$ k\ge2 $时, 对于图$ G $, 若图$ G $的孤立韧度和最小度满足$ \delta(G)\ge I(G)\ge k-\frac{1}{k} $, 则$ G $有分数$ k $-因子.

通过对文献[4]的深入分析, 我们给出如下几个注记:

(1) 在文献[4]中, 对定理2.1的证明忽略了对$ T $中只有$ K_{a} $的情况讨论. 事实上, 通过本文主要定理的证明和反例选取, 会发现真正孤立韧度的界和反例恰好出现在$ T $中只有$ K_{a} $的情况.

(2) 在定理2.1孤立韧度界最好性的说明中, 作者认为在上述所给的例子中令$ S=V(K_{n(a-1)})\cup V(K_{(nb+1)(a-1)}) $, 就有

$ I(G)\le\frac{(nb+1+n)(a-1)}{nb+1}=a-1+\frac{n(a-1)}{nb+1}<a-1+\frac{a-1}{b}. $

进而当$ n\to\infty $时有$ I(G)\to a-1+\frac{a-1}{b} $.

这里关于$ I(G) $的计算是一个明显的错误. 因为根据图$ G $的构造, $ K_{(nb+1)(a-1)} $中只有

$ \{u_{1}, u_{2}, \cdots, u_{nb+1}\} $

这部分顶点与$ (nb+1)K_{1} $相邻, 因此, 只要删除$ V(K_{n(a-1)}) $和$ \{u_{1}, u_{2}, \cdots, u_{nb+1}\} $就可以得到$ nb+1 $个孤立顶点. 从而图$ G $的真实孤立韧度值应该为$ I(G)=\frac{n(a-1)+nb+1}{nb+1}=1+\frac{n(a-1)}{nb+1} $且$ \lim_{n\to\infty}=1+\frac{a-1}{b} $. 由此可知, [4]中的反例无法说明定理2.1中孤立韧度是紧的.

(3) 关于分数$ k $-因子孤立韧度条件的猜想2.2是不成立的. 事实上, [3]中已经给出了$ G $存在分数$ k $-因子的紧孤立韧度条件, 即: 若$ \delta(G)\ge k $且$ I(G)\ge k $, 则$ G $存在分数$ k $-因子. 虽然我们发现[3]中关于$ I(G)\ge k $最好性解释的反例也存在漏洞, 但文献[5]中对此作了补充解释, 给出了正确反例.

基于如上的分析, 可知关于分数$ [a, b] $-因子的紧孤立韧度条件至今没有得到解决, 依然是个开问题. 这引导我们去深入思考到底图中存在分数$ [a, b] $-因子的最好孤立条件是什么. 本文的贡献在于解答这个问题, 给出关于分数$ [a, b] $-因子的孤立韧度下界, 并且通过反例来说明新给出的界是紧的.

本文主要结论如下:

定理3.1  设$ G $是一个图, $ a, b $都是正整数, 且$ 2\le a\le b $. 若$ \delta(G)\ge a $且$ I(G)\ge a-1+\frac{a}{b} $, 则$ G $存在分数$ [a, b] $-因子.

根据分数$ [a, b] $-因子的定义, 最小度条件$ \delta(G)\ge a $显然是紧的. 下面通过实例来解释定理3.1中的孤立韧度也是紧的. 设$ G=K_{\lfloor\frac{al-1}{b}\rfloor}\vee(lK_{a}) $其中$ l\ge2 $是正整数. 为了得到至少两个孤立点, 显然要删除$ K_{\lfloor\frac{al-1}{b}\rfloor} $ 中的所有顶点, 选择$ m $ (其中$ m\in[2, l] $ 是整数) 个$ K_{a} $并对每个$ K_{a} $删除其中的$ a-1 $个顶点. 从而有,

$ I(G)=\min\limits_{m\in\{2, \cdots, l\}}\{\frac{\lfloor\frac{al-1}{b}\rfloor+m(a-1)}{m}\}=a-1+\min\limits_{m\in\{2, \cdots, l\}}\{\frac{\lfloor\frac{al-1}{b}\rfloor}{m}\}. $

设$ al-1=bn+c $, 其中$ n\in\Bbb N\cup\{0\} $, $ c\in\{0, 1, \cdots, b-1\} $. 进而$ \frac{1}{b}\le\frac{c+1}{b}\le1 $,

$ \begin{eqnarray*} I(G)=a-1+\min\limits_{m\in\{2, \cdots, l\}}\{\frac{\frac{al-1-c}{b}}{m}\} =a-1+\frac{\frac{al-1-c}{b}}{l}=a-1+\frac{a}{b}-\frac{1+c}{bl}. \end{eqnarray*} $

可以看到为了让比值达到最小需要取$ m=l $, 同时$ I(G) $的值随着$ l $的增大而增大, 最后逼近于$ a-1+\frac{a}{b} $但无法到达$ a-1+\frac{a}{b} $ (因为图是有限的). 即$ \lim\limits_{l\to+\infty}I(G)=a-1+\frac{a}{b}. $ 设$ S=V(K_{\lfloor\frac{al-1}{b}\rfloor}) $及$ T=V(lK_{a}) $, 则有

$ b|S|-a|T|+\sum\limits_{x\in T}d_{G-S}(x)=b\lfloor\frac{al-1}{b}\rfloor-la. $

若$ al-1 $是$ b $的整数倍, 则

$ b\lfloor\frac{al-1}{b}\rfloor-la=b\frac{al-1}{b}-la=-1. $

若$ al-1 $不是$ b $的整数倍, 则

$ b\lfloor\frac{al-1}{b}\rfloor-la<b\frac{al-1}{b}-la=-1. $

综上所述, $ b|S|-a|T|+\sum_{x\in T}d_{G-S}(x) < 0 $, 根据引理3.3, 可知$ G $没有分数$ [a, b] $-因子.

为了证明定理3.1, 我们需要用到几个引理. 以下结果刻画了分数$ [a, b] $-因子存在的充分必要条件.

引理3.2^[6]  设$ G $是一个图, $ a, b $为正整数且满足$ a\le b $. 则$ G $存在分数$ [a, b] $-因子当且仅当对任意$ S\subseteq V(G) $, 有

$ b|S|-a|T|+\sum\limits_{x\in T}d_{G-S}(x)\ge 0 $

成立, 其中$ T=\{x\in V(G)-S|d_{G-S}(x)\le a\} $.

可知引理3.2中的$ T $由顶点集$ S $决定, 且可以改写为$ T=\{x\in V(G)-S|d_{G-S}(x)\le a-1\} $. 值得注意的是, 引理3.2有如下等价形式.

引理3.3^[6]  设$ G $是一个图, $ a, b $为正整数且满足$ a\le b $. 则$ G $存在分数$ [a, b] $-因子当且仅当

$ b|S|-a|T|+\sum\limits_{x\in T}d_{G-S}(x)\ge 0 $

对任意不相交的顶点子集$ S, T\subseteq V(G) $都成立.

以下引理刻画了特定框架下的独立集和覆盖集.

引理3.4^[7]  设$ G $是一个图, $ H=G[T] $满足对任意$ x\in V(H) $有$ d_{G}(x)= k-1 $且$ H $的任何一个连通分支都不与$ K_{k} $同构, 其中$ T\subseteq V(G) $且$ k\ge2 $为整数. 则存在$ H $的最大独立集$ I $和覆盖集$ C=V(H)-I $满足

$ |V(H)|\le \sum\limits_{i=1}^{k}(k-i+1)|I^{(i)}|-\frac{|I^{(1)}|}{2}\quad \text{和}\quad|C|\le \sum\limits_{i=1}^{k}(k-i)|I^{(i)}|-\frac{|I^{(1)}|}{2}, $

其中$ I^{(i)}=\{x\in I, d_{H}(x)=k-i\} $ ($ 1\le i \le k $)且$ \sum\limits_{i=1}^{k}|I^{(i)}|=|I| $.

若$ G $是完全图, 则根据$ \delta(G)\ge a $可知结果成立. 下面讨论非完全图. 设$ G $满足定理3.1的所有条件, 但不存在分数$ [a, b] $-因子. 根据引理3.3, 存在$ V(G) $的不相交子集$ S $和$ T $满足

$ \begin{equation} b|S|-a|T|+\sum\limits_{x\in T}d_{G-S}(x)=b|S|+\sum\limits_{x\in T}(d_{G-S}(x)-a)\le-1. \end{equation} $

(4.1)

选取$ S $和$ T $使得$ |T| $达到最小. 从而可知$ T\ne\emptyset $, 且对任意$ x\in T $有$ d_{G-S}(x)\le a-1 $.

设$ l $是$ H'=G[T] $中与$ K_{a} $同构的连通分支数, $ T_{0}=\{x\in V(H')| d_{G-S}(x)=0\} $. 设子图$ H $是从$ H'-T_{0} $中删除$ l $个与$ K_{a} $同构的连通分支后得到的子图. 在$ H' $的每个$ K_{a} $连通分支中选取$ a-1 $个顶点构成的顶点子集记为$ S' $.

若$ |V(H)|=0 $, 则由(4.1)可知$ |S|\le \frac{a(|T_{0}|+l)-1}{b} $. 由$ |T|\ne0 $得到$ |T_{0}|+l\ge1 $. 若$ |T_{0}|+l=1 $, 则$ |S|\le \frac{a-1}{b} $进而有$ S=\emptyset $. 由$ d_{G-S}(x)+|S|\ge d_{G}(x)\ge\delta(G)\ge a $可得$ d_{G-S}(x)\ge a-|S|=a $, 这与任意$ x\in T $满足$ d_{G-S}(x)\le a-1 $矛盾. 进而$ i(G-S\cup S')=|T_{0}|+l\ge2 $且

$ \begin{eqnarray*} \label{example} I(G)&\le&\frac{|S\cup S'|}{i(G-S-S')}\le\frac{\lfloor\frac{a(|T_{0}|+l)-1}{b}+l(a-1)\rfloor}{|T_{0}|+l}\\ &\le&\frac{\lfloor(a-1+\frac{a}{b})(|T_{0}|+l)-\frac{1}{b}\rfloor}{|T_{0}|+l}=a-1+\frac{\lfloor\frac{a(|T_{0}|+l)-1}{b}\rfloor}{|T_{0}|+l}. \end{eqnarray*} $

设$ a(|T_{0}|+l)-1=mb+c $, 其中$ m\in\Bbb N\cup\{0\} $且$ c\in\{0, \cdots, b-1\} $. 则$ \frac{1}{b}\le\frac{c+1}{b}\le1, $

$ \begin{eqnarray*} a-1+\max\{\frac{\lfloor\frac{a(|T_{0}|+l)-1}{b}\rfloor}{|T_{0}|+l}\} =a-1+\max\{\frac{\frac{a(|T_{0}|+l)-1}{b}-\frac{c}{b}}{|T_{0}|+l}\} =a-1+\frac{a}{b}+\max\{-\frac{\frac{c+1}{b}}{|T_{0}|+l}\}. \end{eqnarray*} $

这说明$ a-1+\frac{\lfloor\frac{a(|T_{0}|+l)-1}{b}\rfloor}{|T_{0}|+l} $随着$ |T_{0}|+l $的增大而增大, 当$ |T_{0}|+l $逼近于无穷时达到最大, 进而有$ I(G) < a-1+\frac{a}{b} $, 矛盾.

由此有$ |V(H)| > 0 $. 设$ H=H_{1}\cup H_{2} $其中$ H_{1} $是$ H $中的连通分支的并集, 其中对任意$ v\in V(H_{1}) $满足$ d_{G-S}(v)=a-1 $. 且$ H_{2}=H-H_{1} $. 根据引理3.4, $ H_{1} $存在最大独立集$ I_{1} $和覆盖集$ C_{1}=V(H_{1})-I_{1} $满足

$ \begin{equation} |V(H_{1})|\le \sum\limits_{i=1}^{a}(a-i+1)|I^{(i)}|-\frac{|I^{(1)}|}{2}\le (a-\frac{1}{2})|I_{1}|, \end{equation} $

(4.2)

和

$ \begin{equation} |C_{1}|\le \sum\limits_{i=1}^{a}(a-i)|I^{(i)}|-\frac{|I^{(1)}|}{2}, \end{equation} $

(4.3)

其中$ I^{(i)}=\{v\in I_{1}, d_{H_{1}}(v)=a-i\} $($ 1\le i \le a $)且$ \sum\limits_{i=1}^{a}|I^{(i)}|=|I_{1}| $. 根据$ H $和$ H_{2} $的定义, 可知$ H_{2} $的每个连通分支都至少存在一个$ G-S $中度至多为$ a-2 $的顶点. 显然, 若$ H_{2}\ne\emptyset $, 则$ a\ge3 $, 且$ I_{2} $可以通过下面的程序选出: 选择顶点$ v\in V(H_{2}) $使得它在$ G-S $中有最小的度(每次迭代按照原$ G-S $的度进行计算). 若当前所有顶点在原来$ G-S $中的度均为$ a-1 $, 则选择在当前子图中度最小的. 更新$ V(H_{2})\gets V(H_{2})\setminus(\{v\}\cup N_{H_{2}}(v)) $并重复这一过程直到$ V(H_{2})=\emptyset $.

设$ W=V(G)-S-T $且$ U=S\cup S'\cup C_{1}\cup(N_{G}(I_{1})\cap W))\cup N_{G-S}(I_{2})=S\cup S'\cup N_{G-S}(I_{1})\cup N_{G-S}(I_{2}) $. 下面分两种情况讨论.

情况1.  $ |T_{0}|+l\ge1 $.

下面两个断言说明$ H_{1} $或$ H_{2} $都不能单独存在.

断言4.1  若$ |T_{0}|+l\ge1 $, 则$ |I_{2}|\ne0 $.

证  假设$ |I_{2}|=0 $. 由$ |V(H)| > 0 $可知$ |I_{1}|\ne 0 $.

将$ I_{1} $划分为如下两个子集.

$ I_{11} $: $ v\in I_{11} $若存在$ v'\in I_{1}\setminus\{v\} $使得$ N_{G-S}(v)\cap N_{G-S}(v')\ne\emptyset $;

$ I_{12} $: $ v\in I_{12} $若$ N_{G-S}(v) $和$ N_{G-S}(I_{1}\setminus\{v\}) $之间不存在交集.

可得

$ b|S|\le |V(H_{1})|+a|T_{0}|+la-1\le (a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|+a(|T_{0}|+l)-1, $

$ |S|\le (\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|-\frac{1}{b}+\frac{a(|T_{0}|+l)}{b}, $

$ \begin{eqnarray*} &\quad&|S\cup S'\cup N_{G-S}(I_{1})|\\ &\le&(\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|-\frac{1}{b}+\frac{a(|T_{0}|+l)}{b}+l(a-1)+(a-1-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|\\ &=&(a-1+\frac{a}{b}-\frac{b+1}{2b})|I_{11}|+(a-1+\frac{a}{b}-\frac{1}{b})|I_{12}|+\frac{a}{b}|T_{0}|+(a-1+\frac{a}{b})l-\frac{1}{b}\\ &\le&(a-1+\frac{a}{b})(|T_{0}|+l)+(a-1+\frac{a}{b}-\frac{1}{b})|I_{1}|-\frac{1}{b}\\ &\le&(a-1+\frac{a}{b})(|I_{1}|+|T_{0}|+l)-\frac{2}{b} \end{eqnarray*} $

且

$ \begin{eqnarray*} I(G)&\le&\frac{|S\cup S'\cup N_{G-S}(I_{1})|}{i(G-S\cup S'\cup N_{G-S}(I_{1}))}\\ &\le&\frac{\lfloor(a-1+\frac{a}{b})(|I_{1}|+l+|T_{0}|)-\frac{2}{b}\rfloor}{|I_{1}|+l+|T_{0}|}\\ &=&a-1+\frac{\lfloor\frac{a(|I_{1}|+l+|T_{0}|)-2}{b}\rfloor}{|I_{1}|+l+|T_{0}|}\\ &<&a-1+\frac{a}{b}, \end{eqnarray*} $

这与$ I(G)\ge a-1+\frac{a}{b} $矛盾.

断言4.2  若$ |T_{0}|+l\ge1 $, 则$ |I_{1}|\ne0 $.

证  假设$ |I_{1}|=0 $. 根据$ |V(H)| > 0 $有$ |I_{2}|\ne0 $, 进而$ a\ge3 $.

设$ I_{2}=\{v_{1}, v_{2}, \cdots, v_{|I_{2}|}\} $满足$ d_{G-S}(v_{1})\le a-2 $和$ d_{G-S}(v_{1})\le d_{G-S}(v_{2})\le\cdots\le d_{G-S}(v_{|I_{2}|}) $. 则$ |T|=|V(H_{2})|+|T_{0}|+al $,

$ \begin{eqnarray*} b|S|\le a|T|-d_{G-S}(T)-1 \le a|T_{0}|+al+\sum\limits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))-1 \end{eqnarray*} $

且

$ |S|\le\frac{a(|T_{0}|+l)}{b}+\frac{\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))}{b}-\frac{1}{b}. $

可得$ i(G-U)\ge2 $其中$ U=S\cup S'\cup N_{G-S}(I_{2}) $,

$ \begin{eqnarray*} |U|&\le&|S|+|S'|+|N_{G-S}(I_{2})|\\ &\le&\frac{a(|T_{0}|+l)}{b}+\frac{\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))}{b}-\frac{1}{b}+l(a-1)+\sum\limits_{i=1}^{|I_{2}|}d_{G-S}(v_{i})\\ &=&\frac{a|T_{0}|}{b}+l(a-1+\frac{a}{b})+\sum\limits_{i=1}^{|I_{2}|}(-\frac{d_{G-S}^{2}(v_{i})}{b}+\frac{a+b-1}{b}d_{G-S}(v_{i})+\frac{a}{b})-\frac{1}{b}\\ &\le&\frac{a|T_{0}|}{b}+l(a-1+\frac{a}{b})+(-\frac{(a-2)^{2}}{b}+\frac{a+b-1}{b}(a-2)+\frac{a}{b})\\ &\quad&+(|I_{2}|-1)(-\frac{(a-1)^{2}}{b}+\frac{a+b-1}{b}(a-1)+\frac{a}{b})-\frac{1}{b}\\ &=&\frac{a|T_{0}|}{b}+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}. \end{eqnarray*} $

因此,

$ \begin{eqnarray*} I(G)&\le&\frac{|U|}{i(G-U)}\le\frac{\lfloor\frac{a|T_{0}|}{b}+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}\rfloor}{|I_{2}|+|T_{0}|+l}\\ &\le&\frac{\lfloor(a-1+\frac{a}{b})(|T_{0}|+l+|I_{2}|)-1+\frac{a-3}{b}\rfloor}{|I_{2}|+|T_{0}|+l}\\ &=&a-1+\frac{\lfloor\frac{a(|T_{0}|+l+|I_{2}|)+a-3}{b}\rfloor-1}{|I_{2}|+|T_{0}|+l}\\ &<&a-1+\frac{a}{b}, \end{eqnarray*} $

矛盾.

根据断言4.1和断言4.2, 得$ |I_{1}| > 0 $, $ |I_{2}| > 0 $且$ a\ge3 $.

记$ v_{1}, v_{2}, \cdots, v_{|I_{2}|} $是按照断言4.2定义的$ I_{2} $的顶点序列. 则$ |T|=|V(H_{1})|+|V(H_{2})|+|T_{0}|+al $,

$ \begin{eqnarray*} b|S|&\le& a|T|-d_{G-S}(T)-1\\ &\le& a(|T_{0}|+l)+(a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|+\sum\limits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))-1\\ \end{eqnarray*} $

且

$ \begin{eqnarray*} |S|&\le&\frac{a(|T_{0}|+l)+(a-\frac{1}{2})|I_{11}|+(a-1)|I_{12}|+\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))-1}{b}\\ &=&\frac{a}{b}(|T_{0}|+l)+(\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|+\frac{\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))}{b}-\frac{1}{b}. \end{eqnarray*} $

可得$ i(G-U)\ge3 $其中$ U=S\cup S'\cup C_{1}\cup(N_{G}(I_{1})\cap W)\cup N_{G-S}(I_{2}) $且

$ \begin{eqnarray*} |U|&\le&|S|+|S'|+|C_{1}|+|N_{G}(I_{1})\cap W|+|N_{G-S}(I_{2})|\\ &\le&\frac{a}{b}(|T_{0}|+l)+(\frac{a}{b}-\frac{1}{2b})|I_{11}|+\frac{a-1}{b}|I_{12}|+\frac{\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))}{b}\\ &\quad&-\frac{1}{b}+l(a-1)+(a-\frac{1}{2}-1)|I_{11}|+(a-1)|I_{12}|+\sum\limits_{i=1}^{|I_{2}|}d_{G-S}(v_{i})\\ &\le&\frac{a}{b}|T_{0}|+l(a-1+\frac{a}{b})+(a-1+\frac{a}{b}-\frac{1}{b})|I_{1}|+(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}\\ &\le&(|T_{0}|+l)(a-1+\frac{a}{b})+(a-1+\frac{a}{b})|I_{1}|+(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-4}{b}. \end{eqnarray*} $

因此有

$ \begin{eqnarray*} I(G)&\le&\frac{|U|}{i(G-U)}\le\frac{\lfloor(a-1+\frac{a}{b})(|T_{0}|+l+|I_{1}|+|I_{2}|)-1+\frac{a-4}{b}\rfloor}{|I_{1}|+|I_{2}|+|T_{0}|+l}\\ &=&a-1+\frac{\lfloor\frac{a(|I_{1}|+|I_{2}|+|T_{0}|+l)+a-4}{b}\rfloor-1}{|I_{1}|+|I_{2}|+|T_{0}|+l}\\ &<&a-1+\frac{a}{b}, \end{eqnarray*} $

与$ I(G) $的假设矛盾.

情况2.  $ |T_{0}|+l=0 $.

与情况1类似, 下面两个断言是确认$ H_{1} $或$ H_{2} $不能独立存在.

断言4.3  若$ |T_{0}|+l=0 $, 则$ |I_{2}|\ne0 $.

证  若$ |I_{2}|=0 $. 则可得$ |I_{1}|\ne 0 $, $ |T|=|V(H_{1})| $和$ b|S|\le a|T|-d_{G-S}(T)-1=|T|-1 $.

若$ |I_{1}|=1 $, 则$ |T|\le a-1 $且$ |S|\le\frac{|T|-1}{b}\le \frac{a-2}{b} $. 因此$ |S|=0 $且$ a\le\delta(G)\le |S|+(a-1)=a-1 $, 矛盾. 从而有$ |I_{1}|\ge2 $.

进而$ i(G-U)\ge|I_{1}|\ge2 $其中$ U=S\cup C_{1}\cup(N_{G}(I_{1})\cap W) $. 类似断言4.1的推导, 我们有

$ |U|\le|S|+|C_{1}|+\sum\limits_{i=1}^{k}(i-1)|I^{(i)}|\le(a-1+\frac{a-1}{b})|I_{1}|-\frac{1}{b}\le(a-1+\frac{a}{b})|I_{1}|-\frac{3}{b}. $

从而

$ I(G)\le\frac{|U|}{i(G-U)}\le\frac{\lfloor (a-1+\frac{a}{b})|I_{1}|-\frac{3}{b}\rfloor}{|I_{1}|}<a-1+\frac{a}{b}, $

矛盾.

断言4.4  若$ |T_{0}|+l=0 $, 则$ |I_{1}|\ne0 $.

证  假设$ |I_{1}|=0 $. 则根据$ |V(H)| > 0 $有$ |I_{2}|\ne 0 $, 进而$ a\ge3 $.

若$ |I_{2}|=1 $, 则设$ d_{min}=\min\{d_{G-S}(v)|v\in H_{2}\} $, $ z\in V(H_{2}) $满足$ d_{G-S}(z)=d_{min} $, 进而有$ d_{min}\in\{1, \cdots, a-2\} $. 可得

$ b|S|\le a|T|-d_{G-S}(T)-1\le |T|(a-d_{min})-1, $

$ |S|\le\frac{|T|(a-d_{min})-1}{b}\le\frac{(a-1)(a-d_{min})-1}{b} $

且

$ \begin{eqnarray*} &\quad&a\le\delta(G)\le d_{min}+|S|\le d_{min}+\frac{(a-1)(a-d_{min})-1}{b}\\ &=&\frac{a^{2}}{b}-\frac{a}{b}+\frac{(b-a+1)d_{min}}{b}-\frac{1}{b}\\ &\le&\frac{a^{2}}{b}-\frac{a}{b}+\frac{(b-a+1)(a-2)}{b}-\frac{1}{b}\\ &=&a-2+\frac{2a-3}{b}, \end{eqnarray*} $

矛盾.

从而可得$ |I_{2}|\ge2 $. 设$ v_{1}, v_{2}, \cdots, v_{|I_{2}|} $是断言4.2中定义的$ I_{2} $顶点序列, 从而$ d_{G-S}(v_{1})\le a-2 $且$ d_{G-S}(v_{1})\le d_{G-S}(v_{2})\le\cdots\le d_{G-S}(v_{|I_{2}|}) $. 从而有$ |T|=|V(H_{2})| $,

$ \begin{eqnarray*} b|S|&\le& a|T|-d_{G-S}(T)-1\\ &\le& \sum\limits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))-1\\ \end{eqnarray*} $

和

$ |S|\le\frac{\sum\nolimits_{i=1}^{|I_{2}|}(d_{G-S}(v_{i})+1)(a-d_{G-S}(v_{i}))}{b}-\frac{1}{b}. $

根据$ i(G-U)\ge|I_{2}|\ge2 $其中$ U=S\cup N_{G-S}(I_{2}) $, 以及断言4.2中的讨论, 得到

$ |U|\le|S|+|N_{G-S}(I_{2})|\le(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}. $

从而有

$ I(G)\le\frac{|U|}{i(G-U)}\le\frac{\lfloor(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}\rfloor}{|I_{2}|}<a-1+\frac{a}{b}, $

矛盾.

从断言4.3和断言4.4, 可知$ |I_{1}|\ge1 $, $ |I_{2}|\ge1 $且$ a\ge3 $. 可得$ i(G-U)\ge2 $其中$ U=S\cup C_{1}\cup(N_{G}(I_{1})\cap W)\cup N_{G-S}(I_{2}) $且

$ \begin{eqnarray*} |U|&\le&|S|+|C_{1}|+|N_{G}(I_{1})\cap W|+|N_{G-S}(I_{2})|\\ &\le&(a-1+\frac{a-1}{b})|I_{1}|+(a-1+\frac{a}{b})|I_{2}|-1+\frac{a-3}{b}\\ &\le&(a-1+\frac{a}{b})(|I_{1}|+|I_{2}|)-1+\frac{a-4}{b}. \end{eqnarray*} $

从而有

$ \begin{eqnarray*} I(G)&\le&\frac{|U|}{i(G-U)}\le\frac{\lfloor(a-1+\frac{a}{b})(|I_{1}|+|I_{2}|)-1+\frac{a-4}{b}\rfloor}{|I_{1}|+|I_{2}|}\\ &=&a-1+\frac{\lfloor\frac{a(|I_{1}|+|I_{2}|)+a-4}{b}\rfloor-1}{|I_{1}|+|I_{2}|}\\ &<&a-1+\frac{a}{b}, \end{eqnarray*} $

矛盾.

综上所述, 结论成立.