In this paper, we consider the relationship between toughness and the existence of \((g,f)\)-factors with inclusion/exclusion properties. We obtain that if \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\) with \(b > a \geq 2\) and \(a \leq g(x) < f(x) \leq b\) where \(a\), \(b\) are two integers, then for any two given edges \(e_{1}\) and \(e_{2}\), there exists a \((g,f)\)-factor including \(e_{1}\), \(e_{2}\); and a \((g,f)\)-factor including \(e_{1}\) and excluding \(e_{2}\); as well as a \((g,f)\)-factor excluding \(e_{1}\), \(e_{2}\).
All graphs considered are simple and finite. We refer the reader to [2] for terminologies and notations not defined here.
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). For \(x \in V(G)\), we denote by \(d_{G}(x)\) the degree of \(x\) in \(G\) and by \(N_{G}(x)\) the set of vertices adjacent to \(x\) in \(G\). We write \(N_{G}[x]\) for \(N_{G}(x) \cup \{x\}\). The minimum degree of \(G\) is denoted by \(\delta(G)\). For \(S \subseteq V(G)\), let \(N_{G}(S)\) denote the union of \(N_{G}(x)\) for every \(x \in S\). We use \(G[S]\) and \(G-S\) to denote the subgraph induced by \(S\) and \(V(G)-S\).
A subset \(S \subseteq V(G)\) is called an independent set(a covering set) if every edge of \(G\) is incident with at most(at least) one vertex of \(S\). For any disjoint subsets \(S,~T\subseteq V(G)\), \(E_{G}(S,T)\) denotes the set of edges with one end in \(S\) and the other in \(T\) and \(e_{G}(S,T)=|E_{G}(S,T)|\).
Let \(f:V(G) \rightarrow N\) be an integer function. For any subset \(X \subseteq V(G)\), we denote \(f(X)=\sum\limits_{x \in X}f(x)\) and \(f(\emptyset)=0\). A spanning subgraph \(F\) of \(G\) is called an \(f\)-factor of \(G\) satisfying \(d_{F}(x)=f(x)\) for any \(x \in V(G)\). When \(f(x)=k\) for all \(x \in V(G)\), \(F\) is called a \(k\)-factor. Let \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) with \(g(x) \leq f(x)\) for any \(x \in V(G)\). A \((g,f)\)–\(factor\) of \(G\) is a spanning subgraph \(F\) satisfying \(g(x) \leq d_{F}(x) \leq f(x)\) for any \(x \in V(G)\). \(F\) is called an \([a,b]\)–\(factor\) if \(g(x) = a\) and \(f(x) = b\) for any \(x \in V(G)\).
Chvátal [7] first introduced the concept of \(toughness\), \(t(G)\), denoted by \[\begin{aligned} t(G)=min\{\frac{|S|}{\omega(G-S)}: S \subseteq V(G),\omega(G-S) \geq 2\}, \end{aligned}\] where \(\omega(G-S)\) denotes the number of components of \(G-S\) and \(G\) is not a complete graph. If \(G\) is complete, then \(t(G)=\infty\). A graph \(G\) is \(k\)–\(tough\) if \(t(G) \geq k\).
Chvátal mainly studied the relationship between toughness and the existence of Hamilton cycles and \(k\)-factors. He conjectured that every \(k\)-tough graph \(G\) has a \(k\)-factor if \(k|V(G)|\) is even(\(k\) is a positive integer).
Enomoto et al. [9] confirmed Chvátal’s conjecture and showed that the result is sharp.
Chen [5] improved considered \(k\)-factors containing a specified edge or excluding a specified edge under the similar condition.
Theorem 1.1([5]).Let \(G\) be a graph and \(k\geq 2\). If \(t(G)\geq k\) and \(k|V(G)|\) is even, then for every edge \(e\) of \(G\), there exists a \(k\)-factor which contains the given edge \(e\), and there also exists a \(k\)-factor which does not contain \(e\).
As a generalization of Chvátal’s conjecture, Katerinis [12] studied the relationship between toughness and the existence of \(f\)-factors, as well as \([a,b]\)-factor.
Since the toughness condition about \(k\)-factors is sharp, we [4] considered the relationship between toughness condition and the existence of \([a,b]\)-factors for \(b > a \geq 2\). We observed the bound of toughness condition in Theorem 1.2 is sharp.
Theorem 1.2([4]).Let \(G\) be a graph of order \(n\) and \(a\), \(b\) be two positive integers with \(b > a \geq 2\). If \(t(G) \geq a-1 + \frac{a-1}{b}\), then \(G\) has an \([a,b]\)-factor.
Much work has been contributed to the existence of factors with given properties ([1, 13, 16, 17]). Recently, the researchers considered toughness and factors with various conditions([8, 10, 15, 18], [19, 20]). The existence of an even \([4,b]\)-factor in a graph was considered [6]. In this paper, we consider the existence of \((g,f)\)-factors with inclusion/exclusion properties under the condition of toughness when \(a \leq g(x) < f(x) \leq b\), \(b > a \geq 2\).
Theorem 1.3. Let \(G\) be a graph, \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) with \(a \leq g(x) < f(x) \leq b\) for any \(x \in V(G)\) where \(a\), \(b\) are two positive integers with \(b > a \geq 2\). Let \(e_{1}\), \(e_{2}\) be two distinct edges of a graph \(G\). If \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\), then \(G\) contains a \((g,f)\)-factor containing \(e_{1}\) and \(e_{2}\); and a \((g,f)\)-factor containing \(e_{1}\) and excluding \(e_{2}\); as well as a \((g,f)\)-factor excluding \(e_{1}\) and \(e_{2}\);
In order to prove the main theorem, we first give the characterization of \((g,f)\)-factors due to Heinrich [11].
Theorem 2.1 ([11]).Let \(G\) be a graph and \(g\), \(f\) be integer-valued functions defined on \(V(G)\). If \(g(x) < f(x)\) for every \(x \in V(G)\), then \(G\) has a \((g,f)\)-factor if and only if for any subset \(S\) of \(V(G)\), \[\begin{aligned} g(T) – d_{G-S}(T) \leq f(S), \end{aligned}\] where \(T=\{x|x \in V(G) – S,~d_{G-S}(x) \leq g(x)\}\).
The following lemma can be deduced from Theorem 2.1.
Lemma 2.2([14]).Let \(G\) be a graph and \(g\), \(f\) be integer-valued functions defined on \(V(G)\) such that \(g(x) < f(x) \leq d_{G}(x)\) for every \(x \in V(G)\). Let \(E_{1}\) and \(E_{2}\) be two disjoint subsets of \(E(G)\), then \(G\) has a \((g,f)\)-factor \(F\) such that \(E_{1} \subseteq E(F)\) and \(E_{2} \cap E(F) = \emptyset\) if and only if for any disjoint subsets \(S\) and \(T\) of \(V(G)\) \[\begin{aligned} g(T) – d_{G-S}(T) \leq f(S)-\alpha(S,T;E_{1},E_{2})-\beta(S,T;E_{1},E_{2}), \end{aligned}\] where \(U=V(G) – S- T\), \(\alpha(S,T;E_{1},E_{2})=2|E_{1} \cap E_{G}(S)| +|E_{1} \cap E_{G}(S, U)|\) and \(\beta(S,T;E_{1},E_{2})\\=2|E_{2} \cap E_{G}(T)| +|E_{2} \cap E_{G}(T, U)|\).
In addition, the lemmas below are essential to the proof of our main theorem.
Lemma 2.3([14]).Let \(G\) be a graph and \(H=G[T]\) such that \(\delta(H) \geq 1\) and \(1 \leq d_{G}(x) \leq k-1\) for every \(x \in V(H)\) where \(T \subseteq V(G)\) and \(k \geq 2\). Let \(T_{1},\ldots,~T_{k-1}\) be a partition of the vertices of \(H\) satisfying \(d_{G}(x)=j\) for each \(x \in T_{j}\) where we allow some \(T_{j}\) to be empty. If each component of \(H\) has a vertex of degree at most \(k-2\) in \(G\), then \(H\) has a maximal independent set \(I\) and a covering set \(C=V(H)-I\) such that \[\begin{aligned} \sum\limits_{j=1}^{k-1}(k-j)c_{j} \leq \sum\limits_{j=1}^{k-1}(k-2)(k-j)i_{j}, \end{aligned}\] where \(c_{j}=|C \cap T_{j}|\) and \(i_{j}=|I \cap T_{j}|\) for \(j=1,\ldots,~k-1\).
We also need the following lemmas to prove our main theorem.
Lemma 3.1([7]).If a graph \(G\) is not complete, then \(t(G) \leq \frac{1}{2}\delta(G)\).
Lemma 3.2. Let \(G\) be a graph with toughness \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\) and \(g\), \(f\) be integer-valued functions defined on \(V(G)\) such that \(a \leq g(x) < f(x) \leq b\) for every \(x \in V(G)\), where \(a\), \(b\) are integers. Let \(S\), \(T\) be a pair of disjoint subsets of \(V(G)\). If \(S \neq \emptyset\) and \(T \neq \emptyset\), then \[\begin{aligned} g(T)-d_{G-S}(T) \leq f(S) -4. \end{aligned}\]
Proof of Lemma 3.2. By the contrary, suppose that there exists a pair of disjoint subsets \(S\), \(T\) of \(V(G)\) with \(|S| >0\), \(|T|>0\) satisfying \(g(T)-d_{G-S}(T) > f(S) -4\). That is, \[\begin{aligned} \label{eq1} g(T)-d_{G-S}(T) \geq f(S) -3. \end{aligned} \tag{1}\]
Moreover, suppose that \(S\), \(T\) is a pair of minimal sets respect to (1). Then by the minimality of \(S\) and \(T\) we obtain the following claim.
Claim 1.
(1) Given S, if T is a minimal set with respect to (1), then \(d_{G-S}(x) < g(x) \text{ for all }x \in T\).
(2) Given T, if S is a minimal set with respect to (1), then \(d_{T}(x) >a + 1 \text{ for all }x \in S\).
Proof. If \(|T| \geq 2\), by the choice of \(T\), we have for any \(x \in T\), \(g(T-\{x\})-d_{G-S}(T- \{x\}) < f(S) -3\). That is, \(d_{G-S}(x) < g(x)\).
If \(|T| = 1\), let \(T = \{ x \}\). Then we get that \(d_{G-S}(x) \leq g(x)\). And we notice that \(d_{G-S}(x) = g(x)\) holds only when \(d_{G-S}(x)=g(x)=2\) and \(f(S)=3\), it follows that \(a=2\) and \(|S| = 1\). Then \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)} \geq 2\) and \(\delta(G) \geq 2 t(G) \geq 4\) by Lemma 3.1. However, \(d_{G}(x) \leq d_{G-S}(x) + |S| =3\), a contradiction. Therefore, \(d_{G-S}(x) < g(x)\) when \(|T| = 1\).
Similarly, for any \(\upsilon \in S\), we have \(g(T)-d_{G-(S-\{\upsilon\})}(T) < f(S-\{\upsilon\}) -3.\) Hence \(d_{T}(\upsilon) =e_{G}(\upsilon, T) >f(\upsilon) \geq a + 1\). We complete the proof of Claim 1. ◻
Since \(g(x) < f(x) \leq b\), we have \(0 \leq d_{G-S}(x) \leq b-2\) for any \(x \in T\). Let \(T_{i}=\{x \in T | d_{G-S}(x) =i,~~0 \leq i \leq b-2 \}\), \(t_i=|T_i|\). Set \(H=G[T_1 \cup T_2 \cup \cdots \cup T_{b-2}]\). \(T_1 \cup T_2 \cup \cdots \cup T_{b-2}\) is a partition of the vertices of \(H\). By Lemma 2.3, \(H\) has a maximal independent set \(I\) and a covering set \(C\) such that \[\begin{aligned} \label{main2} \sum\limits_{j=1}^{b-2}(b-1-j)c_{j} \leq \sum\limits_{j=1}^{b-2}j(b-1-j)i_{j}, \end{aligned} \tag{2}\] where \(c_{j}=|C \cap T_{j}|\) and \(i_{j}=|I \cap T_{j}|\) for \(j=1,\ldots,~b-2\).
Without the loss of generality, we choose \(I\) to be a maximal independent set of \(H\). Set \(W=V(G)-S-T\) and \(U=S \cup C \cup (N_{G-S}(I) \cap W)\). Then \[\begin{aligned} |U| \leq |S| + \sum\limits_{j=1}^{b-2}ji_{j}, ~~\omega(G-U) \geq t_{0} + \sum\limits_{j=1}^{b-2}i_{j}. \end{aligned}\]
Now we show that \(|U| \geq t(G) \omega (G-U)\).
It holds obviously when \(\omega (G-U) \geq 2\). When \(\omega (G-U) = 1\), for any \(x \in T\), \(|U| \geq d_{G-S}(x)+|S| \geq \delta(G) \geq 2t(G) > t(G) \omega(G-U).\)
Therefore \[\begin{aligned} |S| \geq |U| – \sum\limits_{j=1}^{b-2}ji_{j} \geq \sum\limits_{j=1}^{b-2}(t(G)-j)i_{j} +t(G)t_0. \end{aligned}\]
On the other hand, since \(a \leq g(x) < f(x) \leq b\), \[\begin{aligned} g(T)-d_{G-S}(T) \leq& (b-1)|T| – d_{G-S}(T)\\=& \sum\limits_{j=1}^{b-2}(b-1-j)t_{j} +(b-1)t_{0}\\ =&\sum\limits_{j=1}^{b-2}(b-1-j)i_{j}+\sum\limits_{j=1}^{b-2}(b-1-j)c_{j}+(b-1)t_{0}, \end{aligned}\]
and \(f(S) \geq (a+1) |S|\).
Combined with (1) we have \[\begin{aligned} &\sum\limits_{j=1}^{b-2}(b-1-j)i_{j}+\sum\limits_{j=1}^{b-2}(b-1-j)c_{j}\\ &\qquad \geq (a+1) |S|-3-(b-1)t_{0}\\ &\qquad\geq (a+1)\sum\limits_{j=1}^{b-2}(t(G)-j)i_{j}+((a+1)t(G)-b+1)t_{0}-3. \end{aligned}\]
It follows that \[\begin{aligned} \label{t} \sum\limits_{j=1}^{b-2}(b-1-j)c_{j} \geq& \sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1)\notag\\ &+j)i_{j}+((a+1)t(G)-b+1)t_{0}-3. \end{aligned} \tag{3}\]
Combined with (2), we obtain that \[\begin{aligned} \sum\limits_{j=1}^{b-2}j(b-1-j)i_{j} \geq& \sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1)+j)i_{j}\notag\\&+((a+1)t(G)-b+1)t_{0}-3. \end{aligned}\]
Now we consider the following cases.
Case 1. \(t_{0} > 0\).
In this case, we have \((a+1)t(G)-(b-1) \geq \frac{(a+b)^{2}+2(b-a)-3}{4}-(b-1)=\frac{(a+b-1)^{2}}{4}>3\) since \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\). Therefore there exists some \(j \in \{1,2,\cdots,b-2 \}\) satisfying \(j(b-1-j) >(a+1)t(G)-(a+1)j-(b-1)+j\), that is, \(j(b-1-j)+ (a+1)j-j > (a+1)t(G)-(b-1)\). Meanwhile, \(j(b-1-j)+ (a+1)j-j=-j^{2}+(a+b-1)j \leq \frac{(a+b-1)^{2}}{4}\) and \((a+1)t(G)-(b-1) \geq \frac{(a+b-1)^{2}}{4}\), a contradiction.
Case 2. \(t_{0} = 0\).
In this case, we first show the following claim.
Claim 2. \(C \neq \emptyset\).
Proof. If \(C = \emptyset\), then \(|T|= \sum\limits_{j=1}^{b-2}i_{j}\). By (3), we have \[\begin{aligned} \sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1-j))i_{j} \leq 3. \end{aligned}\]
Since \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\) and \(j \leq b-2\), we get \[\begin{aligned} \frac{(b-a+1)^{2}+4a}{4}|T| \leq \sum\limits_{j=1}^{b-2} (\frac{(b+a-1)^{2}}{4}-aj)i_j \leq 3. \end{aligned}\]
By Claim 1, \(|T| \geq a+2 \geq 4\)(\(b > a \geq 2\)), \(\frac{(b-a+1)^{2}+4a}{4}|T| \geq 4\), a contradiction. ◻
Next we show that for any vertex \(x \in C\), \(d_I(x)=1\). If there exists one vertex in \(C\) with at least two neighbors in \(I\), then \(|U| \leq |S| + \sum\limits_{j=1}^{b-2}ji_{j} -1\). And \(|S| \geq t(G)(t_0 +\sum\limits_{j=1}^{b-2}i_{j})- \sum\limits_{j=1}^{b-2}ji_{j}+1\).
By the inequality (2), it follows that \[\begin{aligned} \sum\limits_{j=1}^{b-2}j(b-1-j)i_{j} \geq& \sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1)\\ &+j)i_{j}+((a+1)t(G)-b+1)t_{0}-3\\ >&\sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1)+j)i_{j}. \end{aligned}\]
Similarly to Case 1, we also obtain a contradiction.
Now, let \(x \in C\) and \(U'=U-\{x\}\). Then \(\omega(G-U')=\sum\limits_{j=1}^{b-2}i_{j}\). Now we show that \(|U'| \geq t(G)(\sum\limits_{j=1}^{b-2}i_{j})\).
It holds obviously when \(\sum\limits_{j=1}^{b-2}i_{j} >1\). If \(\sum\limits_{j=1}^{b-2}i_{j}=1\), set the independent vertex be \(\upsilon\). Then \(|U|=|U' \cup \{ \upsilon \} | \geq |S| +d_{G-S}(\upsilon) \geq \delta(G) \geq 2t(G)\), that is \(|U'| \geq t(G)+(t(G)-1) \geq t(G) = t(G)\sum\limits_{j=1}^{b-2}i_{j}\)\(\left(\text{since }t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)} \geq 1\right)\).
Now we obtain that \(|S| \geq t(G)\sum\limits_{j=1}^{b-2}i_{j}-\sum\limits_{j=1}^{b-2}ji_{j}+1\). By the inequality (2), it follows that \(\sum\limits_{j=1}^{b-2}j(b-1-j)i_{j} > \sum\limits_{j=1}^{b-2}((a+1)t(G)-(a+1)j-(b-1)+j)i_{j}\). Similarly to Case 1, we also obtain a contradiction. The proof is complete. ◻
Now we begin to prove our main results.
Proof of Theorem 1.3. Let \(E_{1}\), \(E_{2}\) be two edge sets with \(E_{1} \cup E_{2} = \{e_{1}, e_{2}\}\). The theorem holds if and only if \(G\) contains a \((g,f)\)-factor \(F\) such that \(E_{1} \subseteq E(F)\), \(E_{2} \cap E(F) = \emptyset\) where \(E_{1}\) or \(E_{2}\) may be empty. By the contrary, suppose that \(G\) does not contain such a \((g,f)\)-factor \(F\). Then, by Lemma 2.2, there exists a pair of disjoint subsets \(S\), \(T\) of \(V(G)\) such that \[\begin{aligned} \label{eq3} g(T) – d_{G-S}(T) > f(S)-\alpha(S,T;E_{1},E_{2})-\beta(S,T;E_{1},E_{2}), \end{aligned} \tag{4}\] where \(W=V(G) – S- T\), \(\alpha(S,T;E_{1},E_{2})=2|E_{1} \cap E_{G}(S)| +|E_{1} \cap E_{G}(S, W)|\) and \(\beta(S,T;E_{1},E_{2})=2|E_{2} \cap E_{G}(T)| +|E_{2} \cap E_{G}(T, W)|\).
Meanwhile, as \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\), \(G\) contains a \((g,f)\)-factor [3]. Therefore, \[\begin{aligned} \label{eq4} g(T) – d_{G-S}(T) \leq f(S). \end{aligned} \tag{5}\]
Now we show the following claim.
Claim. \(S \neq \emptyset\) and \(T \neq \emptyset\).
Proof. If \(S \cup T = \emptyset\), then \(\alpha(S,T;E_{1},E_{2})=\beta(S,T;E_{1},E_{2})=0\), and \(g(T) – d_{G-S}(T) > f(S)\), a contradiction to (5).
Then we consider the following cases.
Case 1. \(S = \emptyset\) and \(T \neq \emptyset\). Then \(\alpha(S,T;E_{1},E_{2})=0\). And we obtain that \(\beta(S,T;E_{1},E_{2}) \neq 0\) from (4) and (5). It follows that \(E_{2} \neq \emptyset\). Hence either \(E_{2} =\{ e_{2} \}\) or \(E_{2} = \{e_{1}, e_{2} \}\).
If \(E_{2} =\{ e_{2} \}\), then \(E_{1} =\{ e_{1} \}\), which is the case of containing \(e_{1}\) and excluding \(e_{2}\). According to (4) again, \[\begin{aligned} g(T) – d_{G}(T) >-2|E_{2} \cap E_{G}(T)| -|E_{2} \cap E_{G}(T, W)|. \end{aligned}\]
Then \(g(T)- d_{G}(T) \leq (b-1- \delta(G))|T| \leq (b-1-2t(G))|T|\) since \(g(T) \leq (b-1)|T|\) and \(\delta(G) \geq 2t(G)\). It follows that \((b-1-2t(G))|T| \leq \frac{1-a^{2}-b^{2}}{2(1+a)} |T| \leq -a|T|\) by \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\). And it yields that \(-a \geq (-a)|T| > -2|E_{2} \cap E_{G}(T)| -|E_{2} \cap E_{G}(T, W)| \geq -2\), contradicting with \(a \geq 2\).
If \(E_{2} =\{e_{1}, e_{2} \}\), then \(E_{1} =\emptyset\), which is the case of excluding \(e_{1}\) and \(e_{2}\). Then \[\begin{aligned} g(T) – d_{G}(T) >-2|E_{2} \cap E_{G}(T)| -|E_{2} \cap E_{G}(T, W)|. \end{aligned}\]
Then \(g(T)- d_{G}(T) \leq (b-1- \delta(G))|T| \leq (b-1-2t(G))|T|\) since \(g(T) \leq (b-1)|T|\) and \(\delta(G) \geq 2t(G)\). It follows that \((b-1-2t(G))|T| \leq \frac{1-a^{2}-b^{2}}{2(1+a)} \leq -a\) by \(t(G) \geq \frac{(a+b)^{2}+2(b-a)-3}{4(a+1)}\). And it yields that \((-a)|T| > -2|E_{2} \cap E_{G}(T)| -|E_{2} \cap E_{G}(T, W)|\).
If \(|T| \geq 2\), then \(-2a > -4\), a contradiction. If \(|T| = 1\), \(2|E_{2} \cap E_{G}(T)| +|E_{2} \cap E_{G}(T, W)| \leq 2\), then \(-2 >(-a)|T|>-2|E_{2} \cap E_{G}(T)| -|E_{2} \cap E_{G}(T, W)| \geq -2\), a contradiction, too.
Case 2. \(S \neq \emptyset\) and \(T = \emptyset\). Then \(\beta(S,T;E_{1},E_{2})=0\). Meanwhile, \(\alpha(S,T;E_{1},E_{2}) \neq 0\). It follows that \(E_{1} \neq \emptyset\). Hence either \(E_{1} =\{ e_{1} \}\) or \(E_{1} = \{e_{1}, e_{2} \}\).
If \(E_{1} =\{ e_{1} \}\), then \(E_{2} =\{ e_{2} \}\), which is the case of including \(e_{1}\) and excluding \(e_{2}\). From (4), we have \(f(S) < \alpha(S,T;E_{1},E_{2}) = 2|E_{1} \cap E_{G}(S)| +|E_{1} \cap E_{G}(S, W)| \leq 2\), which is impossible since \(f > a \geq 2\).
\(E_{1} = \{e_{1}, e_{2} \}\), then \(E_{2} =\emptyset\), which is the case of containing \(e_{1}\) and \(e_{2}\). And \[\begin{aligned} f(S) -2|E_{1} \cap E_{G}(S)| -|E_{1} \cap E_{G}(S, W)| <0. \end{aligned}\]
Then \(f(S)< 2|E_{1} \cap E_{G}(S)| + |E_{1} \cap E_{G}(S, W)|\) as \(f> a \geq 2\), a contradiction. This complete the proof of the claim. ◻
Now since \(S \neq \emptyset\) and \(T \neq \emptyset\), by Lemma 3.2, we have \[\begin{aligned} g(T)-d_{G-S}(T) \leq f(S) -4. \end{aligned}\]
But \(\alpha(S,T;E_{1},E_{2}) + \beta(S,T;E_{1},E_{2}) \leq 4\), it follows from (4) that \[\begin{aligned} g(T)-d_{G-S}(T) > f(S) -4, \end{aligned}\] a contradiction. The proof is complete. ◻