Introduction
For given graphs G G G H H H G G G H H H G G G H H H H H H ex ( n , H ) \operatorname{ex}(n,H) ex ( n , H ) n n n H H H n n n H H H ex ( n , H ) \operatorname{ex}(n,H) ex ( n , H ) H H H EX ( n , H ) \operatorname{EX}(n,H) EX ( n , H ) n n n H H H
For integers n n n p p p T n , p T_{n,p} T n , p p p p n n n t n , p t_{n,p} t n , p T n , p T_{n,p} T n , p [14 ] proved
Theorem 1 ([14 ] ). For all n ≥ p ≥ 2 n \ge p \ge2 n ≥ p ≥ 2 ex ( n , K p ) = t n , p − 1 \operatorname{ex}(n,K_p)=t_{n,p-1} ex ( n , K p ) = t n , p − 1 and EX ( n , K p ) = { T n , p − 1 } \operatorname{EX}(n,K_p)=\{T_{n,p-1}\} EX ( n , K p ) = { T n , p − 1 }
This Turán’s theorem generalizes Mantel’s theorem [11 ] stating that ex ( n , K 3 ) = ⌊ n 2 4 ⌋ \operatorname{ex}(n,K_3)=\left\lfloor\frac{n^2}{4}\right\rfloor ex ( n , K 3 ) = ⌊ 4 n 2 ⌋
We follow the notation and terminology of [1 ] unless stated otherwise. For a graph G G G V ( G ) V(G) V ( G ) E ( G ) E(G) E ( G ) S S S ∣ S ∣ |S| ∣ S ∣ e ( G ) = ∣ E ( G ) ∣ e(G)=|E(G)| e ( G ) = ∣ E ( G ) ∣
The disjoint union of graphs G G G H H H G ∪ H G \cup H G ∪ H G ∨ H G \vee H G ∨ H G G G H H H V ( G ) V(G) V ( G ) V ( H ) V(H) V ( H )
Let K p K_p K p p p p K p ‾ \overline{K_p} K p p p p S ℓ S_\ell S ℓ ℓ + 1 \ell+1 ℓ + 1 k K p kK_p k K p k k k K p K_p K p
Observe that a copy of K p K_p K p G G G p p p G ‾ \overline{G} G ex ( n , H ) \operatorname{ex}(n,H) ex ( n , H )
ex ‾ ( n , H ) = ( n 2 ) − ex ( n , H ) , t ‾ n , p = ( n 2 ) − t n , p and EX ‾ ( n , H ) = { G ‾ : G ∈ EX ( n , H ) } . \overline{\operatorname{ex}}(n,H)=\binom{n}{2}-\operatorname{ex}(n,H),\qquad\overline{t}_{n,p}=\binom{n}{2}-t_{n,p}\quad\text{and}\quad\overline{\operatorname{EX}}(n,H)=\{\overline{G}:G\in\operatorname{EX}(n,H)\}. ex ( n , H ) = ( 2 n ) − ex ( n , H ) , t n , p = ( 2 n ) − t n , p and EX ( n , H ) = { G : G ∈ EX ( n , H )} . Key words and phrases. Turán number, discharging, disjoint cliques.
Research of the first author is supported in part by NSF RTG Grant DMS-1937241.
Research of the second author is supported in part by NSF RTG Grant DMS-1937241.
Research of the fourth author is supported by the Fundamental and Interdisciplinary Disciplines Break-through Plan of the Ministry of Education of China (JYB2025XDXM207).
The problem of determining the Turán number of vertex-disjoint copies of cliques was initiated by Erdős [4 ] . Subsequently, Moon [12 ] and Simonovits [13 ] determined ex ( n , k K p ) \operatorname{ex}(n,kK_p) ex ( n , k K p ) n n n ex ‾ ( n , k K p ) \overline{\operatorname{ex}}(n,kK_p) ex ( n , k K p ) EX ‾ ( n , k K p ) \overline{\operatorname{EX}}(n,kK_p) EX ( n , k K p )
Theorem 2 [12 , 13 ] . Let k ≥ 1 k \ge1 k ≥ 1 p ≥ 2 p \ge2 p ≥ 2 n n n ex ‾ ( n , k K p ) = t ‾ n − k + 1 , p − 1 \overline{\operatorname{ex}}(n,kK_p)=\overline{t}_{n-k+1,p-1} ex ( n , k K p ) = t n − k + 1 , p − 1 EX ‾ ( n , k K p ) = { K ‾ k − 1 ∪ T ‾ n − k + 1 , p − 1 } \overline{\operatorname{EX}}(n,kK_p)=\{\overline{K}_{k-1}\cup\overline{T}_{n-k+1,p-1}\} EX ( n , k K p ) = { K k − 1 ∪ T n − k + 1 , p − 1 }
A natural problem is to determine the Turán numbers of disjoint unions of cliques for all n n n [5 ] determined ex ‾ ( n , k K 2 ) \overline{\operatorname{ex}}(n,kK_2) ex ( n , k K 2 ) EX ‾ ( n , k K 2 ) \overline{\operatorname{EX}}(n,kK_2) EX ( n , k K 2 ) n n n k k k [3 ] determined the Turán number of 2 K p 2K_p 2 K p n n n [18 ] determined the value of ex ( n , K p ∪ K q ) \operatorname{ex}(n,K_p\cup K_q) ex ( n , K p ∪ K q ) n n n q q q p ∈ { 2 , 3 } p\in\{2,3\} p ∈ { 2 , 3 } [7 ] , who determined ex ( n , K p ∪ K q ) \operatorname{ex}(n,K_p\cup K_q) ex ( n , K p ∪ K q ) p p p q q q [10 ] characterized all extremal graphs for K p ∪ K q K_p\cup K_q K p ∪ K q
For positive integers a ≤ b a\le b a ≤ b x , y , n x,y,n x , y , n a x + b y ≤ n ax+by\le n a x + b y ≤ n
K a , b ( n , x , y ) = x K a ∪ y K b ∪ K n − a x − b y (1) K_{a,b}(n,x,y)=xK_a\cup yK_b\cup K_{n-ax-by} \tag*{(1)} K a , b ( n , x , y ) = x K a ∪ y K b ∪ K n − a x − b y (1) Also, for each integer z z z 0 ≤ z ≤ p − 1 0\le z\le p-1 0 ≤ z ≤ p − 1
K 3 , 4 ( n , z ) = { K 3 , 4 ( n , x , y ) : x + 2 y = n − p − q + 1 and x + y ≤ z } , \mathcal{K}_{3,4}(n,z)=\{K_{3,4}(n,x,y):x+2y=n-p-q+1\text{ and }x+y\le z\}, K 3 , 4 ( n , z ) = { K 3 , 4 ( n , x , y ) : x + 2 y = n − p − q + 1 and x + y ≤ z } , and let K 3 , 4 ( n ) = K 3 , 4 ( n , p − 1 ) \mathcal{K}_{3,4}(n)=\mathcal{K}_{3,4}(n,p-1) K 3 , 4 ( n ) = K 3 , 4 ( n , p − 1 )
Theorem 3 [7 , 10 ] . Let n n n p p p q q q p > q ≥ 2 p>q\ge2 p > q ≥ 2 n ≥ p + q n\ge p+q n ≥ p + q
ex ‾ ( n , K p ∪ K q ) = { 3 ( n − p − q + 1 ) , if n ≤ p + q + max { 2 q − p , ⌊ q 2 ⌋ − 1 } , t ‾ n , p − 1 , if n > p + q + max { 2 q − p , ⌊ q 2 ⌋ − 1 } . \overline{\operatorname{ex}}(n,K_p\cup K_q)=
\begin{cases}
3(n-p-q+1), & \text{if }n\le p+q+\max\left\{2q-p,\left\lfloor\frac{q}{2}\right\rfloor-1\right\},\\
\overline{t}_{n,p-1}, & \text{if }n>p+q+\max\left\{2q-p,\left\lfloor\frac{q}{2}\right\rfloor-1\right\}.
\end{cases} ex ( n , K p ∪ K q ) = { 3 ( n − p − q + 1 ) , t n , p − 1 , if n ≤ p + q + max { 2 q − p , ⌊ 2 q ⌋ − 1 } , if n > p + q + max { 2 q − p , ⌊ 2 q ⌋ − 1 } . Furthermore, if p − 1 = q p-1=q p − 1 = q
EX ‾ ( n , K p ∪ K q ) = { K 3 , 4 ( n ) , if n < 4 q , { T ‾ n , p − 1 } , if n ≥ 4 q . \overline{\operatorname{EX}}(n,K_p\cup K_q)=
\begin{cases}
\mathcal{K}_{3,4}(n), & \text{if }n<4q,\\
\{\overline{T}_{n,p-1}\}, & \text{if }n\ge4q.
\end{cases} EX ( n , K p ∪ K q ) = { K 3 , 4 ( n ) , { T n , p − 1 } , if n < 4 q , if n ≥ 4 q . If q + 1 ≤ p − 1 < 3 q 2 q+1\le p-1<\frac{3q}{2} q + 1 ≤ p − 1 < 2 3 q
EX ‾ ( n , K p ∪ K q ) = { K 3 , 4 ( n ) , if n < 3 q , K 3 , 4 ( n ) ∪ { T ‾ n , p − 1 } , if n = 3 q , { T ‾ n , p − 1 } , if n > 3 q . \overline{\operatorname{EX}}(n,K_p\cup K_q)=
\begin{cases}
\mathcal{K}_{3,4}(n), & \text{if }n<3q,\\
\mathcal{K}_{3,4}(n)\cup\{\overline{T}_{n,p-1}\}, & \text{if }n=3q,\\
\{\overline{T}_{n,p-1}\}, & \text{if }n>3q.
\end{cases} EX ( n , K p ∪ K q ) = ⎩ ⎨ ⎧ K 3 , 4 ( n ) , K 3 , 4 ( n ) ∪ { T n , p − 1 } , { T n , p − 1 } , if n < 3 q , if n = 3 q , if n > 3 q . If p − 1 ≥ 3 q 2 p-1\ge\frac{3q}{2} p − 1 ≥ 2 3 q
EX ‾ ( n , K p ∪ K q ) = { K 3 , 4 ( n ) , if n < p − 1 + 3 q , K 3 , 4 ( n ) ∪ { T ‾ n , p − 1 } , if n = p − 1 + 3 q , { T ‾ n , p − 1 } , if n > p − 1 + 3 q . \overline{\operatorname{EX}}(n,K_p\cup K_q)=
\begin{cases}
\mathcal{K}_{3,4}(n), & \text{if }n<p-1+3q,\\
\mathcal{K}_{3,4}(n)\cup\{\overline{T}_{n,p-1}\}, & \text{if }n=p-1+3q,\\
\{\overline{T}_{n,p-1}\}, & \text{if }n>p-1+3q.
\end{cases} EX ( n , K p ∪ K q ) = ⎩ ⎨ ⎧ K 3 , 4 ( n ) , K 3 , 4 ( n ) ∪ { T n , p − 1 } , { T n , p − 1 } , if n < p − 1 + 3 q , if n = p − 1 + 3 q , if n > p − 1 + 3 q . Brualdi and Mellendorf [2 ] and independently Zhang [16 ] determined ex ( k p , k K p ) \operatorname{ex}(kp,kK_p) ex ( k p , k K p ) EX ( k p , k K p ) \operatorname{EX}(kp,kK_p) EX ( k p , k K p ) k k k p p p [17 ] and independently Zhang [16 ] determined the values of ex ( n , 3 K p ) \operatorname{ex}(n,3K_p) ex ( n , 3 K p ) n n n [9 ] determined the values of ex ( n , 4 K p ) \operatorname{ex}(n,4K_p) ex ( n , 4 K p ) EX ( n , 4 K p ) \operatorname{EX}(n,4K_p) EX ( n , 4 K p ) n n n
In this paper, we determine ex ( n , K p ∪ K q ∪ K r ) \operatorname{ex}(n,K_p\cup K_q\cup K_r) ex ( n , K p ∪ K q ∪ K r ) EX ( n , K p ∪ K q ∪ K r ) \operatorname{EX}(n,K_p\cup K_q\cup K_r) EX ( n , K p ∪ K q ∪ K r ) p ≥ q ≥ r ≥ 2 p\ge q\ge r\ge2 p ≥ q ≥ r ≥ 2 n ≥ p + q + r n\ge p+q+r n ≥ p + q + r n = p + q + r n=p+q+r n = p + q + r p = q = r = 2 p=q=r=2 p = q = r = 2 [5 ] , where it was shown that ex ( 6 , 3 K 2 ) = 5 \operatorname{ex}(6,3K_2)=5 ex ( 6 , 3 K 2 ) = 5 EX ( 6 , 3 K 2 ) = { K 1 , 5 } \operatorname{EX}(6,3K_2)=\{K_{1,5}\} EX ( 6 , 3 K 2 ) = { K 1 , 5 }
Theorem 4. Let p ≥ q ≥ r ≥ 2 p\ge q\ge r\ge2 p ≥ q ≥ r ≥ 2 ( p , q , r ) ≠ ( 2 , 2 , 2 ) (p,q,r)\ne(2,2,2) ( p , q , r ) = ( 2 , 2 , 2 ) n = p + q + r n=p+q+r n = p + q + r
ex ‾ ( n , K p ∪ K q ∪ K r ) = min { 6 , t ‾ n , p − 1 } \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\min\{6,\overline{t}_{n,p-1}\} ex ( n , K p ∪ K q ∪ K r ) = min { 6 , t n , p − 1 } and
EX ‾ ( n , K p ∪ K q ∪ K r ) = { { K 4 ∪ K ‾ 3 , K 1 , 6 } , if ( p , q , r ) = ( 3 , 2 , 2 ) , { K 4 ∪ K ‾ n − 4 , T ‾ n , p − 1 } , if ( p , q , r ) = ( 5 , 2 , 2 ) or p ≥ 7 and ( q , r ) = ( 3 , 2 ) , { T ‾ n , p − 1 } , if p ≥ 6 and q = r = 2 , { K 4 ∪ K ‾ n − 4 } , otherwise. \overline{\operatorname{EX}}(n,K_p\cup K_q\cup K_r)=
\begin{cases}
\{K_4\cup\overline{K}_3,K_{1,6}\}, & \text{if }(p,q,r)=(3,2,2),\\
\{K_4\cup\overline{K}_{n-4},\overline{T}_{n,p-1}\}, & \text{if }(p,q,r)=(5,2,2)\\
& \text{or }p\ge7\text{ and }(q,r)=(3,2),\\
\{\overline{T}_{n,p-1}\}, & \text{if }p\ge6\text{ and }q=r=2,\\
\{K_4\cup\overline{K}_{n-4}\}, & \text{otherwise.}
\end{cases} EX ( n , K p ∪ K q ∪ K r ) = ⎩ ⎨ ⎧ { K 4 ∪ K 3 , K 1 , 6 } , { K 4 ∪ K n − 4 , T n , p − 1 } , { T n , p − 1 } , { K 4 ∪ K n − 4 } , if ( p , q , r ) = ( 3 , 2 , 2 ) , if ( p , q , r ) = ( 5 , 2 , 2 ) or p ≥ 7 and ( q , r ) = ( 3 , 2 ) , if p ≥ 6 and q = r = 2 , otherwise. For p ≥ q ≥ r p\ge q\ge r p ≥ q ≥ r c q = { 0 , if p > q , 1 , if p = q , c_q=\begin{cases}0,&\text{if }p>q,\\1,&\text{if }p=q,\end{cases} c q = { 0 , 1 , if p > q , if p = q , c r = { 0 , if p > r , 1 , if p = r . c_r=\begin{cases}0,&\text{if }p>r,\\1,&\text{if }p=r.\end{cases} c r = { 0 , 1 , if p > r , if p = r . c = c q + c r c=c_q+c_r c = c q + c r z z z 0 ≤ z ≤ p − 1 0\le z\le p-1 0 ≤ z ≤ p − 1
K 5 , 6 ( n , z ) = { K 5 , 6 ( n , x , y ) : 2 x + 3 y = n − p − q − r + 1 and x + y ≤ z } , \mathbb{K}_{5,6}(n,z)=\{\mathbb{K}_{5,6}(n,x,y):2x+3y=n-p-q-r+1\text{ and }x+y\le z\}, K 5 , 6 ( n , z ) = { K 5 , 6 ( n , x , y ) : 2 x + 3 y = n − p − q − r + 1 and x + y ≤ z } , and let K 5 , 6 ( n ) = K 5 , 6 ( n , p − 1 ) \mathbb{K}_{5,6}(n)=\mathbb{K}_{5,6}(n,p-1) K 5 , 6 ( n ) = K 5 , 6 ( n , p − 1 ) p = q p=q p = q 3 ( p + q ) 2 − 2 ≤ n ≤ 2 p + 2 q − 4 \frac{3(p+q)}{2}-2\le n\le2p+2q-4 2 3 ( p + q ) − 2 ≤ n ≤ 2 p + 2 q − 4
K 3 , 4 ∗ ( n ) = ( 2 p + 2 q − 4 − n ) K 3 ∪ ( n − 3 ( p + q ) 2 + 2 ) K 4 ∪ K 1 , 3 . K^*_{3,4}(n)=(2p+2q-4-n)K_3\cup\left(n-\frac{3(p+q)}{2}+2\right)K_4\cup K_{1,3}. K 3 , 4 ∗ ( n ) = ( 2 p + 2 q − 4 − n ) K 3 ∪ ( n − 2 3 ( p + q ) + 2 ) K 4 ∪ K 1 , 3 . For p = q = r p=q=r p = q = r 5 ( p + q + r ) 3 − 4 ≤ n ≤ 2 p + 2 q + 2 r − 6 \frac{5(p+q+r)}{3}-4\le n\le2p+2q+2r-6 3 5 ( p + q + r ) − 4 ≤ n ≤ 2 p + 2 q + 2 r − 6
K 5 , 6 ∗ ( n ) = ( 2 p + 2 q + 2 r − 6 − n ) K 5 ∪ ( n − 5 ( p + q + r ) 3 + 4 ) K 6 ∪ K 1 , 5 . K^*_{5,6}(n)=(2p+2q+2r-6-n)K_5\cup\left(n-\frac{5(p+q+r)}{3}+4\right)K_6\cup K_{1,5}. K 5 , 6 ∗ ( n ) = ( 2 p + 2 q + 2 r − 6 − n ) K 5 ∪ ( n − 3 5 ( p + q + r ) + 4 ) K 6 ∪ K 1 , 5 . Our main results are as follows.
Theorem 5. Let n n n p p p q q q r r r p ≥ q ≥ r ≥ 2 p\ge q\ge r\ge2 p ≥ q ≥ r ≥ 2 n ≥ p + q + r + 1 n\ge p+q+r+1 n ≥ p + q + r + 1 s = n − p − q − r + 1 s=n-p-q-r+1 s = n − p − q − r + 1
If n ∈ [ p + q + r + 1 , 4 ( p − 1 ) + c ] n\in[p+q+r+1,4(p-1)+c] n ∈ [ p + q + r + 1 , 4 ( p − 1 ) + c ]
ex ‾ ( n , K p ∪ K q ∪ K r ) = min { 5 s , 3 ( s + r ) , t ‾ n − c , p − 1 } . (2) \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\min\{5s,3(s+r),\overline{t}_{n-c,p-1}\}. \tag*{(2)} ex ( n , K p ∪ K q ∪ K r ) = min { 5 s , 3 ( s + r ) , t n − c , p − 1 } . (2) If n ∈ [ 4 ( p − 1 ) + c , 5 ( p − 1 ) + c ] n\in[4(p-1)+c,5(p-1)+c] n ∈ [ 4 ( p − 1 ) + c , 5 ( p − 1 ) + c ]
ex ‾ ( n , K p ∪ K q ∪ K r ) = min { 5 s , t ‾ n − c , p − 1 } . (3) \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\min\{5s,\overline{t}_{n-c,p-1}\}. \tag*{(3)} ex ( n , K p ∪ K q ∪ K r ) = min { 5 s , t n − c , p − 1 } . (3) If n ≥ 5 ( p − 1 ) + c n\ge5(p-1)+c n ≥ 5 ( p − 1 ) + c ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n − c , p − 1 \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\overline{t}_{n-c,p-1} ex ( n , K p ∪ K q ∪ K r ) = t n − c , p − 1
Theorem 6. Let p ≥ q ≥ r ≥ 2 p\ge q\ge r\ge2 p ≥ q ≥ r ≥ 2 n ≥ p + q + r + 1 n\ge p+q+r+1 n ≥ p + q + r + 1 s = n − p − q − r + 1 s=n-p-q-r+1 s = n − p − q − r + 1 H 0 ( n ) \mathcal{H}_0(n) H 0 ( n ) H 1 ( n ) \mathcal{H}_1(n) H 1 ( n ) H 2 ( n ) \mathcal{H}_2(n) H 2 ( n ) EX ‾ ( n , K p ∪ K q ∪ K r ) = H 0 ( n ) ∪ H 1 ( n ) ∪ H 2 ( n ) \overline{\operatorname{EX}}(n,K_p\cup K_q\cup K_r)=\mathcal{H}_0(n)\cup\mathcal{H}_1(n)\cup\mathcal{H}_2(n) EX ( n , K p ∪ K q ∪ K r ) = H 0 ( n ) ∪ H 1 ( n ) ∪ H 2 ( n ) H 0 ( n ) \mathcal{H}_0(n) H 0 ( n ) K p K_p K p H 1 ( n ) \mathcal{H}_1(n) H 1 ( n ) K p K_p K p K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q H 2 ( n ) \mathcal{H}_2(n) H 2 ( n ) K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q
(1) If c = 0 c=0 c = 0 H 0 ( n ) = { G = T ‾ n , p − 1 : ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n , p − 1 } \mathcal{H}_0(n)=\{G=\overline{T}_{n,p-1}:\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\overline{t}_{n,p-1}\} H 0 ( n ) = { G = T n , p − 1 : ex ( n , K p ∪ K q ∪ K r ) = t n , p − 1 }
H 1 ( n ) = { G ∈ K 3 , 4 ( n , q − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } , \mathcal{H}_1(n)=\{G\in\mathbb{K}_{3,4}(n,q-1):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=3(s+r)\}, H 1 ( n ) = { G ∈ K 3 , 4 ( n , q − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} , and
H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s } . \mathcal{H}_2(n)=\{G\in\mathbb{K}_{5,6}(n,r-1):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=5s\}. H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 5 s } . (2) If c = 1 c=1 c = 1 H 0 ( n ) = ∅ \mathcal{H}_0(n)=\varnothing H 0 ( n ) = ∅
H 1 ( n ) = { G ∈ K 3 , 4 ( n ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } \mathcal{H}_1(n)=\{G\in K_{3,4}(n):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=3(s+r)\} H 1 ( n ) = { G ∈ K 3 , 4 ( n ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} ∪ { G = K 3 , 4 ∗ ( n ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) and 3 ( p + q ) 2 − 2 ≤ n ≤ 2 p + 2 q − 4 } \qquad\cup\{G=K^*_{3,4}(n):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=3(s+r)\ \text{and}\ \frac{3(p+q)}{2}-2\le n\le2p+2q-4\} ∪ { G = K 3 , 4 ∗ ( n ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) and 2 3 ( p + q ) − 2 ≤ n ≤ 2 p + 2 q − 4 } ∪ { G = K 1 ∪ T ‾ n − 1 , p − 1 : ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n − 1 , p − 1 } . \qquad\cup\{G=K_1\cup\overline{T}_{n-1,p-1}:\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\overline{t}_{n-1,p-1}\}. ∪ { G = K 1 ∪ T n − 1 , p − 1 : ex ( n , K p ∪ K q ∪ K r ) = t n − 1 , p − 1 } . and
H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s } . \mathcal{H}_2(n)=\{G\in K_{5,6}(n,r-1):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=5s\}. H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 5 s } . (3) If c = 2 c=2 c = 2 H 0 ( n ) = ∅ \mathcal{H}_0(n)=\varnothing H 0 ( n ) = ∅ H 1 ( n ) = ∅ \mathcal{H}_1(n)=\varnothing H 1 ( n ) = ∅
H 2 ( n ) = { K 5 , 6 ( n ) , if n ≤ 5 p − 5 , K 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n ) } , if 5 p − 4 ≤ n ≤ 6 p − 6 , { K 2 ∪ T ‾ n − 2 , p − 1 } , n ≥ 6 p − 5. \mathcal{H}_2(n)=
\begin{cases}
K_{5,6}(n), & \text{if }n\le5p-5,\\
K_{5,6}(n)\cup\{K^*_{5,6}(n)\}, & \text{if }5p-4\le n\le6p-6,\\
\{K_2\cup\overline{T}_{n-2,p-1}\}, & n\ge6p-5.
\end{cases} H 2 ( n ) = ⎩ ⎨ ⎧ K 5 , 6 ( n ) , K 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n )} , { K 2 ∪ T n − 2 , p − 1 } , if n ≤ 5 p − 5 , if 5 p − 4 ≤ n ≤ 6 p − 6 , n ≥ 6 p − 5. These results extend and generalize Theorem 3 as well as the result for ex ‾ ( n , K p ∪ K p ∪ K p ) \overline{\operatorname{ex}}(n,K_p\cup K_p\cup K_p) ex ( n , K p ∪ K p ∪ K p ) [15 , 16 , 17 ] . The key idea is to consider graphs that already have independent sets P P P Q Q Q R R R r ≥ 2 r\ge2 r ≥ 2 n ≥ p + q + 1 n\ge p+q+1 n ≥ p + q + 1 ex ‾ ( n , K p ∪ K q ∪ K 1 ) = ex ‾ ( n , K p ∪ K q ) \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_1)=\overline{\operatorname{ex}}(n,K_p\cup K_q) ex ( n , K p ∪ K q ∪ K 1 ) = ex ( n , K p ∪ K q )
The structure of the paper is as follows. In the next section, we introduce some more notation and give some definitions. In § 3 we present Theorem 7 on existence of two cliques when we know that one of them exists. § 4 establishes Theorem 8, a generalization of Theorem 7 that addresses another important special case of the main theorem. The subsequent three sections are devoted to proving Theorem 8 by considering several distinct cases. We prove Theorems 4 , 5 and 6 in § 8 , § 9 and § 10 respectively, and conclude the paper with some remarks in § 11 .
Notation and definitions
For a vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) H ⊆ G H\subseteq G H ⊆ G S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) N H ( v ) N_H(v) N H ( v ) N S ( v ) N_S(v) N S ( v ) v v v H H H S S S v v v G G G d G ( v ) = ∣ N G ( v ) ∣ d_G(v)=\lvert N_G(v)\rvert d G ( v ) = ∣ N G ( v )∣ G G G δ ( G ) \delta(G) δ ( G ) Δ ( G ) \Delta(G) Δ ( G ) G ‾ \overline{G} G G G G α ( G ) \alpha(G) α ( G )
Given vertex subsets V 1 , V 2 ⊆ V ( G ) V_1,V_2\subseteq V(G) V 1 , V 2 ⊆ V ( G ) E [ V 1 , V 2 ] E[V_1,V_2] E [ V 1 , V 2 ] V 1 V_1 V 1 V 2 V_2 V 2 e [ V 1 , V 2 ] = ∣ E [ V 1 , V 2 ] ∣ e[V_1,V_2]=\lvert E[V_1,V_2]\rvert e [ V 1 , V 2 ] = ∣ E [ V 1 , V 2 ]∣ V ′ ⊆ V ( G ) V'\subseteq V(G) V ′ ⊆ V ( G ) V ′ V' V ′ G [ V ′ ] G[V'] G [ V ′ ]
The following definition originates from [8 ] . We will use it throughout the proofs.
Definition 1. Given a graph G G G P = ( V 1 , … , V k ) \mathcal{P}=(V_1,\ldots,V_k) P = ( V 1 , … , V k ) V ( G ) V(G) V ( G ) D D D P \mathcal{P} P V ( D ) = { V 1 , … , V k } V(D)=\{V_1,\ldots,V_k\} V ( D ) = { V 1 , … , V k } E ( D ) = { V i V j : ∃ x ∈ V i , N G ( x ) ∩ V j = ∅ } E(D)=\{V_iV_j:\exists x\in V_i,N_G(x)\cap V_j=\varnothing\} E ( D ) = { V i V j : ∃ x ∈ V i , N G ( x ) ∩ V j = ∅ }
When the partition P \mathcal{P} P D D D V i V j ∈ E ( D ) V_iV_j\in E(D) V i V j ∈ E ( D ) x ∈ V i x\in V_i x ∈ V i N G ( x ) ∩ V j = ∅ N_G(x)\cap V_j=\varnothing N G ( x ) ∩ V j = ∅ x x x V j V_j V j V i 1 , V i 2 , … , V i ℓ ∈ V ( D ) V_{i_1},V_{i_2},\ldots,V_{i_\ell}\in V(D) V i 1 , V i 2 , … , V i ℓ ∈ V ( D ) V i j V_{i_j} V i j 1 ≤ j ≤ ℓ − 1 1\le j\le\ell-1 1 ≤ j ≤ ℓ − 1 v i j v_{i_j} v i j V i j + 1 V_{i_{j+1}} V i j + 1 V i 1 V i 2 … V i ℓ V_{i_1}V_{i_2}\ldots V_{i_\ell} V i 1 V i 2 … V i ℓ D D D D D D V j ∈ V ( D ) V_j\in V(D) V j ∈ V ( D ) V i ∈ V ( D ) V_i\in V(D) V i ∈ V ( D ) V i V_i V i V j V_j V j V i V_i V i V j V_j V j A \mathcal{A} A D D D B = V ( D ) ∖ A \mathcal{B}=V(D)\setminus\mathcal{A} B = V ( D ) ∖ A A = ⋃ A A=\bigcup\mathcal{A} A = ⋃ A B = ⋃ B B=\bigcup\mathcal{B} B = ⋃ B u ∈ B u\in B u ∈ B v ∈ A v\in A v ∈ A u v uv uv solo edge if v v v u u u u u u v v v solo neighbors of each other.
Two cliques
Theorem 7. Let p ≥ q ≥ 2 p\ge q\ge2 p ≥ q ≥ 2 n ≥ p + q n\ge p+q n ≥ p + q s = n − p − q + 1 s=n-p-q+1 s = n − p − q + 1 n n n G G G K p K_p K p e ( G ) ≤ 3 s e(G)\le3s e ( G ) ≤ 3 s
(a) G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q
(b) e ( G ) = 3 s e(G)=3s e ( G ) = 3 s G G G x x x K 3 K_3 K 3 y y y K 4 K_4 K 4 3 x + 6 y = 3 s 3x+6y=3s 3 x + 6 y = 3 s 3 x + 4 y ≤ n 3x+4y\le n 3 x + 4 y ≤ n K 1 K_1 K 1
(c) e ( G ) = 3 s e(G)=3s e ( G ) = 3 s p = q p=q p = q G G G K 1 , 3 K_{1,3} K 1 , 3 K 3 K_3 K 3 K 4 K_4 K 4
Proof. Suppose there is a counter-example G G G P ⊂ V ( G ) P\subset V(G) P ⊂ V ( G ) G [ P ] = K ‾ p G[P]=\overline{K}_p G [ P ] = K p e ( G ) ≤ 3 s e(G)\le3s e ( G ) ≤ 3 s e ( G ) = 3 s e(G)=3s e ( G ) = 3 s
Let Q Q Q G − P G-P G − P q ′ = ∣ Q ∣ q'=|Q| q ′ = ∣ Q ∣ S = V ( G ) − P − Q S=V(G)-P-Q S = V ( G ) − P − Q s ′ = ∣ S ∣ s'=|S| s ′ = ∣ S ∣ 1 ≤ q ′ ≤ q − 1 1\le q'\le q-1 1 ≤ q ′ ≤ q − 1 s ′ ≥ s s'\ge s s ′ ≥ s
Suppose first that s ′ = 1 s'=1 s ′ = 1 n ≥ p + q n\ge p+q n ≥ p + q q ′ = q − 1 q'=q-1 q ′ = q − 1 s ′ = s = 1 s'=s=1 s ′ = s = 1 n = p + q n=p+q n = p + q e ( G ) ≤ 3 s = 3 e(G)\le3s=3 e ( G ) ≤ 3 s = 3 P P P
G − P has the fewest edges. (4) G-P\text{ has the fewest edges.} \tag*{(4)} G − P has the fewest edges. (4) Note that S ∪ Q = V ( G ) − P S\cup Q=V(G)-P S ∪ Q = V ( G ) − P G − P G-P G − P u v ∈ E ( G ) uv\in E(G) uv ∈ E ( G ) u , v ∈ S ∪ Q u,v\in S\cup Q u , v ∈ S ∪ Q
(a) If u or v has no neighbors in P , then each w ∈ P has a neighbor in Q ∪ S . (b) If u or v has exactly one neighbor w in P , then w has another neighbor in Q ∪ S . (5) \begin{aligned}
\text{(a)}\quad&\text{If }u\text{ or }v\text{ has no neighbors in }P,\text{ then each }w\in P\text{ has a neighbor in }Q\cup S.\\
\text{(b)}\quad&\text{If }u\text{ or }v\text{ has exactly one neighbor }w\text{ in }P,\text{ then }w\text{ has another neighbor in }Q\cup S. \tag*{(5)}
\end{aligned} (a) (b) If u or v has no neighbors in P , then each w ∈ P has a neighbor in Q ∪ S . If u or v has exactly one neighbor w in P , then w has another neighbor in Q ∪ S . (5) Indeed, if (3.2a) or (3.2b) does not hold, then we switch u u u v v v w w w
Now since e ( G ) ≤ 3 e(G)\le3 e ( G ) ≤ 3 ∣ E ( P , Q ∪ S ) ∣ = 2 |E(P,Q\cup S)|=2 ∣ E ( P , Q ∪ S ) ∣ = 2 ∣ P ∣ = 2 |P|=2 ∣ P ∣ = 2 w ∈ P w\in P w ∈ P u u u v v v
If some w ∈ P w\in P w ∈ P u u u v v v G G G G G G w ∈ P w\in P w ∈ P u u u v v v ∣ P ∣ = 2 |P|=2 ∣ P ∣ = 2 p = q = 2 p=q=2 p = q = 2 ∣ Q ∣ = q ′ = 1 |Q|=q'=1 ∣ Q ∣ = q ′ = 1 u u u S S S v v v Q Q Q ∣ E ( P , Q ∪ S ) ∣ = 2 |E(P,Q\cup S)|=2 ∣ E ( P , Q ∪ S ) ∣ = 2 u u u v v v P P P e ( G ) = 3 e(G)=3 e ( G ) = 3 G = K 1 , 3 G=K_{1,3} G = K 1 , 3 G , G, G , s ′ ≥ 2 s'\ge2 s ′ ≥ 2
We choose a triple ( G , P , Q ) (G,P,Q) ( G , P , Q )
(M1) n : = ∣ V ( G ) ∣ n:=|V(G)| n := ∣ V ( G ) ∣
(M2) subject to (M1), q ′ = ∣ Q ∣ q'=|Q| q ′ = ∣ Q ∣
(M3) subject to (M1) and (M2), the number of vertices in P P P
Claim 3.1. For each u ∈ S ∪ Q u\in S\cup Q u ∈ S ∪ Q d G ( u ) ≤ 2 d_G(u)\le2 d G ( u ) ≤ 2
Proof. Suppose the claim does not hold. Among different choices of P P P u ∈ S ∪ Q u\in S\cup Q u ∈ S ∪ Q d ( u ) ≥ 3 d(u)\ge3 d ( u ) ≥ 3 d ( u ) d(u) d ( u ) K 3 K_3 K 3 u u u
Consider G ′ = G − u G'=G-u G ′ = G − u P P P G ′ G' G ′ K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q G G G n n n e ( G ′ ) ≥ 3 ( s − 1 ) e(G')\ge3(s-1) e ( G ′ ) ≥ 3 ( s − 1 ) G ′ G' G ′ K 3 K_3 K 3 K 4 K_4 K 4 K 1 K_1 K 1 K 1 , 3 K_{1,3} K 1 , 3 p = q p=q p = q d ( u ) ≥ 3 d(u) \ge3 d ( u ) ≥ 3 d ( u ) = 3 d(u)=3 d ( u ) = 3 e ( G ) = 3 s e(G)=3s e ( G ) = 3 s
Case 1: u u u K 4 K_4 K 4 F F F G G G F F F G G G v v v Q ∪ S Q \cup S Q ∪ S u u u P P P v ∈ S ∪ Q v \in S \cup Q v ∈ S ∪ Q d G ( v ) > d G ( u ) d_G(v)>d_G(u) d G ( v ) > d G ( u ) u u u v ∈ P v \in P v ∈ P u u u v v v u u u F − u F-u F − u K 3 K_3 K 3 G ′ G' G ′ G ′ G' G ′ G G G
Since this case is impossible and any P P P K 4 K_4 K 4 G G G
G does not contain K 4 . (6) G\text{ does not contain }K_4. \tag*{(6)} G does not contain K 4 . (6) Case 2: u u u K 3 K_3 K 3 F F F G G G F − u F-u F − u K 4 K_4 K 4 G ′ G' G ′ F − u F-u F − u K 1 , 3 K_{1,3} K 1 , 3 Y Y Y G ′ G' G ′ e ( G ′ ) = 3 ( s − 1 ) e(G')=3(s-1) e ( G ′ ) = 3 ( s − 1 ) p = q p=q p = q Y Y Y K 3 K_3 K 3 e ( G ′ ) = 3 ( s − 1 ) e(G')=3(s-1) e ( G ′ ) = 3 ( s − 1 ) K 3 K_3 K 3 G ′ G' G ′ s − 2 s-2 s − 2 n − 1 = 4 + 3 ( s − 2 ) n-1=4+3(s-2) n − 1 = 4 + 3 ( s − 2 ) s = p s=p s = p Y Y Y v v v u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) v v v p p p G ′ G' G ′ Q ∪ S Q \cup S Q ∪ S d G ( v ) = 4 > 3 = d G ( u ) d_G(v)=4>3=d_G(u) d G ( v ) = 4 > 3 = d G ( u ) u u u
Thus, F − u F-u F − u K 3 K_3 K 3 Y Y Y { v 1 , v 2 , v 3 } \{v_1,v_2,v_3\} { v 1 , v 2 , v 3 } N ( u ) ∩ V ( Y ) = { v 1 , v 2 } N(u) \cap V(Y)=\{v_1,v_2\} N ( u ) ∩ V ( Y ) = { v 1 , v 2 } d ( u ) = 3 d(u)=3 d ( u ) = 3 v 1 , v 2 v_1,v_2 v 1 , v 2 K 3 K_3 K 3 G G G v 1 , v 2 v_1,v_2 v 1 , v 2 P P P u u u
Case 3: Vertex u u u K 3 K_3 K 3 G G G G ′ G' G ′ K 1 , 3 K_{1,3} K 1 , 3 F F F v v v v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 n n n G ′ G' G ′ e ( G ′ ) = 3 ( s − 1 ) e(G')=3(s-1) e ( G ′ ) = 3 ( s − 1 ) p = q p=q p = q G ′ − F G'-F G ′ − F K 3 K_3 K 3 K 3 K_3 K 3 G ′ G' G ′ s − 2 s-2 s − 2 s = p s=p s = p v v v p p p G ′ G' G ′ v ∈ Q ∪ S v \in Q \cup S v ∈ Q ∪ S u v ∈ E ( G ) uv \in E(G) uv ∈ E ( G ) d G ( v ) = 4 > 3 = d G ( u ) d_G(v)=4>3=d_G(u) d G ( v ) = 4 > 3 = d G ( u ) u u u u v ∉ E ( G ) uv \notin E(G) uv ∈ / E ( G ) 1 ≤ i ≤ s − 2 1 \le i \le s-2 1 ≤ i ≤ s − 2 K 3 K_3 K 3 Z i Z_i Z i { v i , 1 , v i , 2 , v i , 3 } \{v_{i,1},v_{i,2},v_{i,3}\} { v i , 1 , v i , 2 , v i , 3 }
By Case 2, u u u Z i Z_i Z i N ( u ) ∩ Z i ⊆ { v i , 3 } N(u) \cap Z_i \subseteq\{v_{i,3}\} N ( u ) ∩ Z i ⊆ { v i , 3 } i ∈ [ s − 2 ] i \in[s-2] i ∈ [ s − 2 ] { v 1 , 1 , … , v s − 2 , 1 , v 1 , v 2 } \{v_{1,1},\ldots,v_{s-2,1},v_1,v_2\} { v 1 , 1 , … , v s − 2 , 1 , v 1 , v 2 } { v 1 , 2 , … , v s − 2 , 2 , u , v } \{v_{1,2},\ldots,v_{s-2,2},u,v\} { v 1 , 2 , … , v s − 2 , 2 , u , v } p p p G G G G G G
The remaining possibility is that each component of G ′ G' G ′ K 3 K_3 K 3 K 1 K_1 K 1 u u u K 3 K_3 K 3 G ′ G' G ′ v 1 , v 2 , … , v k 1 v_1,v_2,\ldots,v_{k_1} v 1 , v 2 , … , v k 1 K 3 K_3 K 3 Z 1 , … , Z k 3 Z_1,\ldots,Z_{k_3} Z 1 , … , Z k 3 V ( Z i ) = { v i , 1 , v i , 2 , v i , 3 } V(Z_i)=\{v_{i,1},v_{i,2},v_{i,3}\} V ( Z i ) = { v i , 1 , v i , 2 , v i , 3 } i = 1 , … , k 3 i=1,\ldots,k_3 i = 1 , … , k 3 n − 1 = k 1 + 3 k 3 n-1=k_1+3k_3 n − 1 = k 1 + 3 k 3
Since 3 k 3 = e ( G ′ ) = e ( G ) − 3 = 3 s − 3 3k_3=e(G')=e(G)-3=3s-3 3 k 3 = e ( G ′ ) = e ( G ) − 3 = 3 s − 3 v ( G ′ ) = k 1 + 3 k 3 v(G')=k_1+3k_3 v ( G ′ ) = k 1 + 3 k 3 k 3 = s − 1 k_3=s-1 k 3 = s − 1 p + q + s = n + 1 = k 1 + 3 ( s − 1 ) + 2 p+q+s=n+1=k_1+3(s-1)+2 p + q + s = n + 1 = k 1 + 3 ( s − 1 ) + 2
p + q − 1 = k 1 + 2 ( s − 1 ) . (7) p+q-1=k_1+2(s-1). \tag*{(7)} p + q − 1 = k 1 + 2 ( s − 1 ) . (7) Since P P P K 3 K_3 K 3 u u u G G G Q ′ Q' Q ′ P P P u u u K 3 K_3 K 3 G G G ( s − 1 ) + 1 = ∣ Q ′ ∣ ≤ q − 1 (s-1)+1=|Q'|\le q-1 ( s − 1 ) + 1 = ∣ Q ′ ∣ ≤ q − 1 q ≥ s + 1 q \ge s+1 q ≥ s + 1 k 1 ≥ 3 k_1 \ge3 k 1 ≥ 3 p = q = s + 1 p=q=s+1 p = q = s + 1
If k 1 ≥ 4 k_1 \ge4 k 1 ≥ 4
q ≤ ⌊ ( p + q ) / 2 ⌋ ≤ ( s − 1 ) + ⌊ ( k 1 + 1 ) / 2 ⌋ ≤ ( s − 1 ) + k 1 − 2. (8) q \le\lfloor(p+q)/2 \rfloor\le(s-1)+\lfloor(k_1+1)/2 \rfloor\le(s-1)+k_1-2. \tag*{(8)} q ≤ ⌊( p + q ) /2 ⌋ ≤ ( s − 1 ) + ⌊( k 1 + 1 ) /2 ⌋ ≤ ( s − 1 ) + k 1 − 2. (8) So, since u u u k 1 − 3 k_1-3 k 1 − 3 K 1 K_1 K 1 q q q Q ′ Q' Q ′ u u u u u u s − 1 s-1 s − 1 K 3 K_3 K 3 q − 1 − ( s − 1 ) q-1-(s-1) q − 1 − ( s − 1 ) G ′ G' G ′ u u u p p p P ′ P' P ′ Q ′ Q' Q ′ s − 1 s-1 s − 1 K 3 K_3 K 3 p − ( s − 1 ) p-(s-1) p − ( s − 1 ) G ′ G' G ′ Q ′ Q' Q ′ (7) , there are p − ( s − 1 ) p-(s-1) p − ( s − 1 ) G ′ G' G ′ Q ′ Q' Q ′ G G G k 1 = 3 k_1=3 k 1 = 3 p = q = s + 1 p=q=s+1 p = q = s + 1
Since u u u Z i Z_i Z i v 1 , 1 , … , v s − 1 , 1 v_{1,1},\ldots,v_{s-1,1} v 1 , 1 , … , v s − 1 , 1 u u u u u u v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 u v 1 ∉ E ( G ) uv_1\notin E(G) u v 1 ∈ / E ( G ) ( s + 1 ) (s+1) ( s + 1 ) Q 1 = { v 1 , 1 , … , v s − 1 , 1 , u , v 1 } Q_1=\{v_{1,1},\ldots,v_{s-1,1},u,v_1\} Q 1 = { v 1 , 1 , … , v s − 1 , 1 , u , v 1 } P 1 = { v 1 , 2 , … , v s − 1 , 2 , v 2 , v 3 } P_1=\{v_{1,2},\ldots,v_{s-1,2},v_2,v_3\} P 1 = { v 1 , 2 , … , v s − 1 , 2 , v 2 , v 3 } G G G G G G K 1 , 3 K_{1,3} K 1 , 3 u u u K 3 K_3 K 3 Theorem 7 holds.
□ \square □
Now let D D D ( P , Q , S ) (P,Q,S) ( P , Q , S ) Q Q Q S ∈ A S\in\mathcal{A} S ∈ A S , Q S,Q S , Q ∣ Q ∣ |Q| ∣ Q ∣ S ∈ B S\in\mathcal{B} S ∈ B
(M4) ∣ B ∣ |\mathcal{B}| ∣ B ∣
There are two cases for ∣ B ∣ |\mathcal{B}| ∣ B ∣
Case 1. ∣ B ∣ = 1 |\mathcal{B}|=1 ∣ B ∣ = 1 B = { S } \mathcal{B}=\{S\} B = { S } A = { P , Q } \mathcal{A}=\{P,Q\} A = { P , Q } S S S P P P Q Q Q u ∈ S u\in S u ∈ S P P P Q Q Q p u ∈ P p_u\in P p u ∈ P q u ∈ Q q_u\in Q q u ∈ Q
Since u u u P − { p u } P-\{p_u\} P − { p u } d G ( u ) ≤ 2 d_G(u)\leq2 d G ( u ) ≤ 2 d G ( p u ) ≤ 2 d_G(p_u)\leq2 d G ( p u ) ≤ 2 p u p_u p u u u u P P P P P P p u p_u p u Q Q Q N Q ( p u ) = ∅ N_Q(p_u)=\varnothing N Q ( p u ) = ∅ P − p u + u P-p_u+u P − p u + u p p p Q ∪ { p u } Q\cup\{p_u\} Q ∪ { p u } Q Q Q p u p_u p u Q Q Q q u ′ q'_u q u ′ d G ( p u ) = 2 d_G(p_u)=2 d G ( p u ) = 2
Thus each u ∈ S u\in S u ∈ S u p u up_u u p u u q u uq_u u q u p u q u ′ p_uq'_u p u q u ′ 3 s ′ 3s' 3 s ′ 3 s ′ 3s' 3 s ′ u p u up_u u p u u q u uq_u u q u u u u p u q u ′ = p v q v ′ p_uq'_u=p_vq'_v p u q u ′ = p v q v ′ u , v ∈ S u,v\in S u , v ∈ S P P P u u u v v v Q Q Q d G ( p u ) = 2 d_G(p_u)=2 d G ( p u ) = 2 p u ≠ p v p_u\ne p_v p u = p v u ≠ v u\ne v u = v e ( G ) ≥ 3 s ′ ≥ 3 s e(G)\geq3s'\geq3s e ( G ) ≥ 3 s ′ ≥ 3 s e ( G ) ≤ 3 s e(G)\leq3s e ( G ) ≤ 3 s s ′ = s s'=s s ′ = s G G G u p u up_u u p u u q u uq_u u q u p u q u ′ p_uq'_u p u q u ′
We now identify the structure. For each u ∈ S u\in S u ∈ S q u = q u ′ q_u=q'_u q u = q u ′ G [ { u , p u , q u } ] ≅ K 3 G[\{u,p_u,q_u\}]\cong K_3 G [{ u , p u , q u }] ≅ K 3 u ∈ S u\in S u ∈ S q u ≠ q u ′ q_u\ne q'_u q u = q u ′ u u u q u p u q u ′ q_up_uq'_u q u p u q u ′ C C C G G G t t t S S S t t t P P P t + 1 t+1 t + 1 Q Q Q u ∈ C ∩ S u\in C\cap S u ∈ C ∩ S q u ≠ q u ′ q_u\ne q'_u q u = q u ′ s < q ≤ p s<q\leq p s < q ≤ p w ∈ P w\in P w ∈ P C C C 3 t + 1 3t+1 3 t + 1 P C P_C P C Q C Q_C Q C t + 1 t+1 t + 1 P ∩ C P\cap C P ∩ C P C P_C P C Q ∩ C Q\cap C Q ∩ C Q C Q_C Q C w w w P P P Q Q Q P P P Q Q Q p p p q q q
Suppose that there is some cycle component C C C t t t S S S t t t P P P Q Q Q P C P_C P C t t t Q C Q_C Q C t + 1 t+1 t + 1 P C P_C P C Q ∩ C Q \cap C Q ∩ C Q C Q_C Q C P P P Q Q Q p p p q q q
Then each component in G G G K 3 K_3 K 3 { u , p u , q u } \{u,p_u,q_u\} { u , p u , q u } u ∈ S u \in S u ∈ S G G G
Case 2. ∣ B ∣ = 2 |\mathcal{B}| = 2 ∣ B ∣ = 2 A = { Q } \mathcal{A} = \{Q\} A = { Q } B = { P , S } \mathcal{B} = \{P,S\} B = { P , S } S ∪ P S \cup P S ∪ P Q Q Q
e [ S ∪ P , Q ] ≥ s ′ + p . (9) e[S \cup P,Q] \ge s' + p. \tag*{(9)} e [ S ∪ P , Q ] ≥ s ′ + p . (9) By Claim 3.1, each vertex of Q Q Q s ′ + p ≤ e [ S ∪ P , Q ] ≤ 2 q ′ s' + p \le e[S \cup P,Q] \le2q' s ′ + p ≤ e [ S ∪ P , Q ] ≤ 2 q ′ p ≥ q ≥ q ′ + 1 p \ge q \ge q' + 1 p ≥ q ≥ q ′ + 1 s ≤ s ′ ≤ q ′ ≤ q − 1 ≤ p − 1 s \le s' \le q' \le q - 1 \le p - 1 s ≤ s ′ ≤ q ′ ≤ q − 1 ≤ p − 1 S P ∉ E ( D ) SP \notin E(D) S P ∈ / E ( D ) S S S P P P e [ S , P ] ≥ s ′ e[S,P] \ge s' e [ S , P ] ≥ s ′ e ( G ) ≥ s ′ + p + s ′ ≥ 3 s + 1 e(G) \ge s' + p + s' \ge3s + 1 e ( G ) ≥ s ′ + p + s ′ ≥ 3 s + 1 S P ∈ E ( D ) SP \in E(D) S P ∈ E ( D ) z ∈ S z \in S z ∈ S P P P w ∈ P w \in P w ∈ P d G ( w ) ≥ 3 d_G(w) \ge3 d G ( w ) ≥ 3 P − w + z P-w+z P − w + z Δ ( G ) ≤ 2 \Delta(G) \le2 Δ ( G ) ≤ 2
Subject to (M1)–(M3), choose ( P , Q ) (P,Q) ( P , Q ) ∑ v ∈ Q d G ( v ) \sum_{v \in Q} d_G(v) ∑ v ∈ Q d G ( v )
If u ∈ S ∪ P has a solo neighbor v ∈ Q , then d ( u ) ≥ d ( v ) . (10) \text{If }u \in S \cup P\text{ has a solo neighbor }v \in Q,\text{ then }d(u) \ge d(v). \tag*{(10)} If u ∈ S ∪ P has a solo neighbor v ∈ Q , then d ( u ) ≥ d ( v ) . (10) Indeed, if d G ( u ) < d G ( v ) d_G(u) < d_G(v) d G ( u ) < d G ( v ) u u u Q Q Q v v v S S S u ∈ P u \in P u ∈ P S P ∈ E ( D ) SP \in E(D) S P ∈ E ( D ) P P P ∑ v ∈ Q d G ( v ) \sum_{v \in Q} d_G(v) ∑ v ∈ Q d G ( v )
Now we assign each vertex of S ∪ P S \cup P S ∪ P Q Q Q s ′ + p s' + p s ′ + p
Distribute the charges so that each edge inside G [ S ∪ P ] G[S \cup P] G [ S ∪ P ] 1 / 2 1/2 1/2 S ∪ P S \cup P S ∪ P Q Q Q Δ ( G ) ≤ 2 \Delta(G) \le2 Δ ( G ) ≤ 2 Q Q Q s ′ + p ≤ e ( G [ S ∪ P ] ) + q ′ s' + p \le e(G[S \cup P]) + q' s ′ + p ≤ e ( G [ S ∪ P ]) + q ′
With (3.5), we have that
e ( G ) ≥ e ( G [ S ∪ P ] ) + e [ S ∪ P , Q ] ≥ s ′ + p − q ′ + ( s ′ + p ) ≥ ( s + 1 ) + ( s ′ + p ) ≥ 3 s + 1 , e(G) \ge e(G[S \cup P]) + e[S \cup P,Q] \ge s' + p - q' + (s' + p) \ge(s+1) + (s' + p) \ge3s + 1, e ( G ) ≥ e ( G [ S ∪ P ]) + e [ S ∪ P , Q ] ≥ s ′ + p − q ′ + ( s ′ + p ) ≥ ( s + 1 ) + ( s ′ + p ) ≥ 3 s + 1 , a contradiction. □
Setup for 3 cliques
In this section we set up a proof of Theorem 8 below, and in the following three sections we prove it.
Theorem 8. Let p , q ≥ r ≥ 2 p, q \ge r \ge2 p , q ≥ r ≥ 2 n ≥ p + r + q n \ge p+r+q n ≥ p + r + q s = n − p − q − r + 1 s = n-p-q-r+1 s = n − p − q − r + 1 n n n G G G K p K_p K p K q K_q K q e ( G ) ≤ 5 s e(G) \le5s e ( G ) ≤ 5 s
(a) G G G K p K_p K p K q K_q K q K r K_r K r
(b) e ( G ) = 5 s e(G) = 5s e ( G ) = 5 s G G G x x x K 5 K_5 K 5 y y y K 6 K_6 K 6 10 x + 15 y = 5 s 10x + 15y = 5s 10 x + 15 y = 5 s 5 x + 6 y ≤ n 5x + 6y \le n 5 x + 6 y ≤ n
(c) e ( G ) = 5 s e(G) = 5s e ( G ) = 5 s p = q = r p = q = r p = q = r G G G K 1 , 5 K_{1,5} K 1 , 5 K 5 K_5 K 5 K 6 K_6 K 6
Note that p p p q q q G G G P , Q ⊆ V ( G ) P,Q \subseteq V(G) P , Q ⊆ V ( G ) G [ P ] = K p G[P]=K_p G [ P ] = K p G [ Q ] = K q ‾ G[Q]=\overline{K_q} G [ Q ] = K q e ( G ) ≤ 5 s e(G)\leq5s e ( G ) ≤ 5 s e ( G ) = 5 s e(G)=5s e ( G ) = 5 s
Let R R R G − P − Q G-P-Q G − P − Q r ′ = ∣ R ∣ r'=|R| r ′ = ∣ R ∣ S = V ( G ) − P − Q − R S=V(G)-P-Q-R S = V ( G ) − P − Q − R s ′ = ∣ S ∣ s'=|S| s ′ = ∣ S ∣ 1 ≤ r ′ ≤ r − 1 1\leq r'\leq r-1 1 ≤ r ′ ≤ r − 1 s ′ ≥ s s'\geq s s ′ ≥ s
Suppose first that s ′ = 1 s'=1 s ′ = 1 n ≥ p + q + r n\geq p+q+r n ≥ p + q + r r ′ = r − 1 r'=r-1 r ′ = r − 1 s ′ = s s'=s s ′ = s n = p + q + r n=p+q+r n = p + q + r
Choose P P P Q Q Q
(Q1) G − P − Q G-P-Q G − P − Q
(Q2) modulo (Q1), ∑ v ∈ S ∪ R d ( v ) \sum_{v\in S\cup R}d(v) ∑ v ∈ S ∪ R d ( v )
Note that S ∪ R = V ( G ) − P − Q S\cup R=V(G)-P-Q S ∪ R = V ( G ) − P − Q G − P − Q G-P-Q G − P − Q x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x , y ∈ S ∪ R x,y\in S\cup R x , y ∈ S ∪ R
(A) If x (or y ) has no neighbors in some J ∈ { P , Q } , then each w ∈ J has a neighbor in R ∪ S ; and (B) If x (or y ) has exactly one neighbor w in some J ∈ { P , Q } , then w has another neighbor in R ∪ S . (11) \begin{aligned}
&\text{(A) If }x\text{ (or }y\text{) has no neighbors in some }J\in\{P,Q\}\text{, then each }w\in J\text{ has a}\\
&\text{neighbor in }R\cup S\text{; and}\\
&\text{(B) If }x\text{ (or }y\text{) has exactly one neighbor }w\text{ in some }J\in\{P,Q\}\text{, then }w\text{ has another}\\
&\text{neighbor in }R\cup S\text{.} \tag*{(11)}
\end{aligned} (A) If x (or y ) has no neighbors in some J ∈ { P , Q } , then each w ∈ J has a neighbor in R ∪ S ; and (B) If x (or y ) has exactly one neighbor w in some J ∈ { P , Q } , then w has another neighbor in R ∪ S . (11) Indeed, if (A) or (B) does not hold, then we switch x x x y y y w w w
Now (11) yields
For each J ∈ { P , Q } , e [ J , R ∪ S ] ≥ 2 with equality only if ∣ J ∣ = 2 or some w ∈ J is adjacent to both x and y . (12) \text{For each }J\in\{P,Q\},\quad e[J,R\cup S]\geq2\text{ with equality only if }|J|=2\text{ or some }w\in J\text{ is adjacent to both }x\text{ and }y. \tag*{(12)} For each J ∈ { P , Q } , e [ J , R ∪ S ] ≥ 2 with equality only if ∣ J ∣ = 2 or some w ∈ J is adjacent to both x and y . (12) Since e ( G ) ≤ 5 e(G)\leq5 e ( G ) ≤ 5 (12) implies that e ( G ) = 5 e(G)=5 e ( G ) = 5 e [ P , Q ] = 0 e[P,Q]=0 e [ P , Q ] = 0 J ∈ { P , Q } J\in\{P,Q\} J ∈ { P , Q } w J w_J w J R ∪ S R\cup S R ∪ S w P w_P w P Q Q Q v ∈ Q v\in Q v ∈ Q P P P R ∪ S R\cup S R ∪ S P − w P + v P-w_P+v P − w P + v w ∈ P w\in P w ∈ P R ∪ S R\cup S R ∪ S (12) , ∣ P ∣ = 2 |P|=2 ∣ P ∣ = 2 P = { w , w ′ } P=\{w,w'\} P = { w , w ′ } ∣ R ∣ = 1 |R|=1 ∣ R ∣ = 1 R ∪ S = { x , y } R\cup S=\{x,y\} R ∪ S = { x , y } w w w w ′ w' w ′ R ∪ S R\cup S R ∪ S x w , x w ′ ∈ E ( G ) xw,xw'\in E(G) x w , x w ′ ∈ E ( G )
Now, if Q Q Q z z z x x x y y y z z z x x x S ∪ R S\cup R S ∪ R (12) , ∣ Q ∣ = 2 |Q|=2 ∣ Q ∣ = 2 Q = { z , z ′ } Q=\{z,z'\} Q = { z , z ′ } z z z z ′ z' z ′ R ∪ S R\cup S R ∪ S y y y P ′ = { w , y } P'=\{w,y\} P ′ = { w , y } Q ′ = { z , x } Q'=\{z,x\} Q ′ = { z , x } R ′ = { w ′ , z ′ } R'=\{w',z'\} R ′ = { w ′ , z ′ } G = K 1 , 5 G=K_{1,5} G = K 1 , 5 s ′ ≥ 2 s'\geq2 s ′ ≥ 2
We choose a quadruple ( G , P , Q , R ) (G,P,Q,R) ( G , P , Q , R )
(N1) n : = ∣ V ( G ) ∣ n:=|V(G)| n := ∣ V ( G ) ∣
(N2) modulo (N1), r ′ r' r ′
(N3) modulo (N1) and (N2), the number of vertices in P ∪ Q P\cup Q P ∪ Q 5 5 5
Claim 4.1. For every x ∈ S ∪ R x\in S\cup R x ∈ S ∪ R d ( x ) ≤ 4 d(x)\leq4 d ( x ) ≤ 4
Proof. Suppose the claim does not hold. Among different choices of P , Q P,Q P , Q x ∈ S ∪ R x\in S\cup R x ∈ S ∪ R d ( x ) ≥ 5 d(x)\geq5 d ( x ) ≥ 5 d ( x ) d(x) d ( x ) K 5 K_5 K 5 x x x
Consider G ′ = G − x G'=G-x G ′ = G − x P P P Q Q Q G ′ G' G ′ K p ‾ \overline{K_p} K p K q ‾ \overline{K_q} K q K r ‾ \overline{K_r} K r G G G n n n 5 ( s − 1 ) 5(s-1) 5 ( s − 1 ) G ′ G' G ′ K 5 K_5 K 5 K 6 K_6 K 6 K 1 K_1 K 1 K 1 , 5 K_{1,5} K 1 , 5 p = q = r p=q=r p = q = r d ( x ) ≥ 5 d(x) \ge5 d ( x ) ≥ 5 d ( x ) = 5 d(x)=5 d ( x ) = 5
Case 1: x x x K 6 K_6 K 6 F F F G G G F F F G G G R ∪ S R \cup S R ∪ S x x x P ∪ Q P \cup Q P ∪ Q F − x F-x F − x K 5 K_5 K 5 G ′ G' G ′ G ′ G' G ′ G G G
Since Case 1 is impossible and any P ∪ Q P \cup Q P ∪ Q K 6 K_6 K 6 G G G
G does not contain K 6 . (13) G\text{ does not contain }K_6. \tag*{(13)} G does not contain K 6 . (13) Case 2: x x x K 5 K_5 K 5 F F F G G G F − x F-x F − x K 6 K_6 K 6 G ′ G' G ′ K 1 , 5 K_{1,5} K 1 , 5 K 5 K_5 K 5 y ∈ V ( G ) − V ( F ) y \in V(G)-V(F) y ∈ V ( G ) − V ( F ) F − x F-x F − x F − x F-x F − x K 5 K_5 K 5 G G G P ∪ Q P \cup Q P ∪ Q x x x
Case 3: For any choice of P , Q P,Q P , Q x ∈ V ( G ) ∖ ( P ∪ Q ) x \in V(G) \setminus(P \cup Q) x ∈ V ( G ) ∖ ( P ∪ Q ) d ( x ) = 5 d(x)=5 d ( x ) = 5 x x x K 5 K_5 K 5 G G G x x x G ′ G' G ′ G ′ G' G ′ K 1 , 5 K_{1,5} K 1 , 5 F F F c c c y 1 , … , y 5 y_1,\ldots,y_5 y 1 , … , y 5 p = q = r p=q=r p = q = r n n n K 5 K_5 K 5 G ′ G' G ′ k k k K 5 K_5 K 5 p = q = r = k + 2 p=q=r=k+2 p = q = r = k + 2
It follows that we can include any two vertices from each copy of K 5 K_5 K 5 P ∪ Q P \cup Q P ∪ Q x x x K 5 K_5 K 5 c c c P P P Q Q Q x c ∉ E ( G ) xc \notin E(G) x c ∈ / E ( G ) P , Q P,Q P , Q R R R P P P { y 1 , y 2 } \{y_1,y_2\} { y 1 , y 2 } Q Q Q { y 3 , y 4 } \{y_3,y_4\} { y 3 , y 4 } R R R { c , x } \{c,x\} { c , x } k k k K 5 K_5 K 5 G G G
The remaining possibility is that each component of G ′ G' G ′ K 5 K_5 K 5 K 1 K_1 K 1 x x x K 5 K_5 K 5 G G G K 1 , 5 K_{1,5} K 1 , 5 K 1 K_1 K 1 k 1 k_1 k 1 K 5 K_5 K 5 k 5 k_5 k 5 G ′ ′ G'' G ′′ G G G K 5 K_5 K 5 n ′ ′ = ∣ V ( G ′ ′ ) ∣ n''=|V(G'')| n ′′ = ∣ V ( G ′′ ) ∣ n = 5 k 5 + k 1 + 6 n=5k_5+k_1+6 n = 5 k 5 + k 1 + 6 n ′ ′ = k 1 + 6 n''=k_1+6 n ′′ = k 1 + 6 e ( G ) = 10 k 5 + 5 e(G)=10k_5+5 e ( G ) = 10 k 5 + 5 s = 2 k 5 + 1 s=2k_5+1 s = 2 k 5 + 1 p + q + r = 3 k 5 + k 1 + 6 p+q+r=3k_5+k_1+6 p + q + r = 3 k 5 + k 1 + 6
Since G ′ G' G ′ P P P Q Q Q K 5 K_5 K 5 P ∪ Q P \cup Q P ∪ Q x x x K 5 K_5 K 5 G G G
r ≥ 2 + k 5 . (14) r \ge2+k_5. \tag*{(14)} r ≥ 2 + k 5 . (14) It follows that V ( G ′ ′ ) V(G'') V ( G ′′ ) p − k 5 p-k_5 p − k 5 q − k 5 q-k_5 q − k 5 r − k 5 r-k_5 r − k 5 G ′ ′ G'' G ′′
1 + k 1 ≤ r − k 5 ≤ ⌊ n ′ ′ / 3 ⌋ = ⌊ k 1 / 3 ⌋ + 2. (15) 1+k_1 \le r-k_5 \le\left\lfloor n''/3 \right\rfloor= \left\lfloor k_1/3 \right\rfloor+ 2. \tag*{(15)} 1 + k 1 ≤ r − k 5 ≤ ⌊ n ′′ /3 ⌋ = ⌊ k 1 /3 ⌋ + 2. (15) By (4.5), k 1 = 0 k_1=0 k 1 = 0 r − k 5 ≤ 2 r-k_5 \le2 r − k 5 ≤ 2 n ′ ′ = 6 n''=6 n ′′ = 6 p , q ≥ r p,q \ge r p , q ≥ r r − k 5 = q − k 5 = p − k 5 = 2 r-k_5=q-k_5=p-k_5=2 r − k 5 = q − k 5 = p − k 5 = 2 □ \square □
Similarly, we obtain the following properties:
(i) If x ∈ R ∪ S has no neighbor in some J ∈ { P , Q } , then d ( v ) ≤ 4 for every v ∈ J ; (ii) If x ∈ S ∪ R has a unique neighbor x ′ in some J ∈ { P , Q } , then d ( x ′ ) ≤ 4. (16) \begin{aligned}
\text{(i)}\ &\text{If }x \in R \cup S\text{ has no neighbor in some }J \in\{P,Q\},\text{ then }d(v) \le4\text{ for every }v \in J;\\
\text{(ii)}\ &\text{If }x \in S \cup R\text{ has a unique neighbor }x'\text{ in some }J \in\{P,Q\},\text{ then }d(x') \le4. \tag*{(16)}
\end{aligned} (i) (ii) If x ∈ R ∪ S has no neighbor in some J ∈ { P , Q } , then d ( v ) ≤ 4 for every v ∈ J ; If x ∈ S ∪ R has a unique neighbor x ′ in some J ∈ { P , Q } , then d ( x ′ ) ≤ 4. (16) With the partition ( P , Q , R , S ) (P,Q,R,S) ( P , Q , R , S ) V ( G ) V(G) V ( G ) D D D R R R R R R A A A D D D B = V ( D ) ∖ A \mathcal{B}=V(D)\setminus\mathcal{A} B = V ( D ) ∖ A S S S S , R S,R S , R D D D R R R S ∈ B S\in\mathcal{B} S ∈ B ( G , P , Q , R ) (G,P,Q,R) ( G , P , Q , R )
(N4) ∣ B ∣ |\mathcal{B}| ∣ B ∣ minimum .
By above, ∣ B ∣ ∈ { 1 , 2 , 3 } |\mathcal{B}|\in\{1,2,3\} ∣ B ∣ ∈ { 1 , 2 , 3 }
Case of ∣ B ∣ = 1 |\mathcal{B}|=1 ∣ B ∣ = 1
In this section, B = { S } \mathcal{B}=\{S\} B = { S } A = { P , Q , R } \mathcal{A}=\{P,Q,R\} A = { P , Q , R } x ∈ S x\in S x ∈ S V ′ ∈ A V'\in\mathcal{A} V ′ ∈ A Δ ( G [ S ] ) ≤ 1 \Delta(G[S])\le1 Δ ( G [ S ]) ≤ 1 s ≤ s ′ ≤ 2 r − 2 s\le s'\le2r-2 s ≤ s ′ ≤ 2 r − 2
e ( G [ S ] ) ≥ t s ′ , r − 1 = { 0 , if 0 ≤ s ′ ≤ r − 1 , s ′ − r + 1 , if r ≤ s ′ ≤ 2 r − 2. (17) e(G[S])\ge t_{s',r-1}=
\begin{cases}
0, & \text{if } 0\le s'\le r-1,\\
s'-r+1, & \text{if } r\le s'\le2r-2.
\end{cases} \tag*{(17)} e ( G [ S ]) ≥ t s ′ , r − 1 = { 0 , s ′ − r + 1 , if 0 ≤ s ′ ≤ r − 1 , if r ≤ s ′ ≤ 2 r − 2. (17) Claim 5.1. If v ∈ P v\in P v ∈ P v ∈ Q v\in Q v ∈ Q u ∈ S u\in S u ∈ S Q R ∈ E ( D ) QR\in E(D) QR ∈ E ( D ) P R ∈ E ( D ) PR\in E(D) P R ∈ E ( D ) N Q ( v ) ≠ ∅ N_Q(v)\ne\varnothing N Q ( v ) = ∅ N P ( v ) ≠ ∅ N_P(v)\ne\varnothing N P ( v ) = ∅ N R ( v ) ≠ ∅ N_R(v)\ne\varnothing N R ( v ) = ∅
Proof. By symmetry, we may assume that v ∈ P v\in P v ∈ P Q R ∈ E ( D ) QR\in E(D) QR ∈ E ( D ) N Q ( v ) = ∅ N_Q(v)=\varnothing N Q ( v ) = ∅ u u u P P P v v v Q Q Q Q R QR QR R R R
If N R ( v ) = ∅ N_R(v)=\varnothing N R ( v ) = ∅ u u u P P P v v v R R R R R R □ \square □
:::
Claim 5.2. No vertex v ∈ V ′ ∈ A v\in V'\in\mathcal{A} v ∈ V ′ ∈ A S S S
Proof. Assume that v ∈ V ′ ∈ A v\in V'\in\mathcal{A} v ∈ V ′ ∈ A u 1 , u 2 ∈ S u_1,u_2\in S u 1 , u 2 ∈ S V ′ ≠ R V'\ne R V ′ = R D D D V ′ , R V',R V ′ , R v ′ ∈ V ′ v'\in V' v ′ ∈ V ′ V ′ V' V ′ V ′ , R V',R V ′ , R v ≠ v ′ v\ne v' v = v ′ V ′ , R V',R V ′ , R u 1 , u 2 u_1,u_2 u 1 , u 2 V ′ V' V ′ v v v S S S R R R □ \square □
:::
Claim 5.3. Every vertex in V ′ ∈ { P , Q } V'\in\{P,Q\} V ′ ∈ { P , Q } S S S A ∖ { V ′ } \mathcal{A}\setminus\{V'\} A ∖ { V ′ }
Proof. By symmetry, we let V ′ = P V'=P V ′ = P v ∈ P v\in P v ∈ P u ∈ S u\in S u ∈ S Q R ∉ E ( D ) QR\notin E(D) QR ∈ / E ( D ) e [ Q , R ] ≥ q e[Q,R]\ge q e [ Q , R ] ≥ q P R , Q P ∈ E ( D ) PR,QP\in E(D) P R , QP ∈ E ( D ) v ′ ∈ Q v'\in Q v ′ ∈ Q u ′ ∈ S u'\in S u ′ ∈ S N P ( v ′ ) ≠ ∅ N_P(v')\ne\varnothing N P ( v ′ ) = ∅ S S S A \mathcal{A} A x x x S S S Q Q Q s ′ − x s'-x s ′ − x S S S Q Q Q Δ ( G [ S ] ) ≤ 1 \Delta(G[S])\le1 Δ ( G [ S ]) ≤ 1 ⌈ x 2 ⌉ \left\lceil\frac{x}{2}\right\rceil ⌈ 2 x ⌉ S S S Q Q Q
e [ S , Q ] + e [ Q , P ] ≥ x + 2 ( s ′ − x ) + ⌈ x 2 ⌉ = 2 s ′ − ⌊ x 2 ⌋ ≥ 2 s ′ − x 2 ≥ 3 s ′ 2 . e[S,Q]+e[Q,P]\ge x+2(s'-x)+\left\lceil\frac{x}{2}\right\rceil=2s'-\left\lfloor\frac{x}{2}\right\rfloor\ge2s'-\frac{x}{2}\ge\frac{3s'}{2}. e [ S , Q ] + e [ Q , P ] ≥ x + 2 ( s ′ − x ) + ⌈ 2 x ⌉ = 2 s ′ − ⌊ 2 x ⌋ ≥ 2 s ′ − 2 x ≥ 2 3 s ′ . By Claim 5.1, N R ( v ) ≠ ∅ N_R(v)\ne\varnothing N R ( v ) = ∅ e [ S , P ] + e [ P , R ] ≥ 3 s ′ 2 e[S,P]+e[P,R]\ge\frac{3s'}{2} e [ S , P ] + e [ P , R ] ≥ 2 3 s ′
e ( G ) = e ( G [ S ] ) + ( e [ S , P ] + e [ P , R ] ) + ( e [ S , Q ] + e [ Q , P ] ) + e [ S , R ] + e [ Q , R ] ≥ t s ′ , r − 1 + 3 s ′ 2 + 3 s ′ 2 + s ′ + q = 4 s ′ + q + t s ′ , r − 1 . \begin{aligned}
e(G)&=e(G[S])+(e[S,P]+e[P,R])+(e[S,Q]+e[Q,P])+e[S,R]+e[Q,R]\\
&\ge t_{s',r-1}+\frac{3s'}{2}+\frac{3s'}{2}+s'+q\\
&=4s'+q+t_{s',r-1}.
\end{aligned} e ( G ) = e ( G [ S ]) + ( e [ S , P ] + e [ P , R ]) + ( e [ S , Q ] + e [ Q , P ]) + e [ S , R ] + e [ Q , R ] ≥ t s ′ , r − 1 + 2 3 s ′ + 2 3 s ′ + s ′ + q = 4 s ′ + q + t s ′ , r − 1 . Since q ≥ r q \ge r q ≥ r e ( G ) > 5 s e(G)>5s e ( G ) > 5 s e ( G ) ≤ 5 s e(G)\le5s e ( G ) ≤ 5 s Q R ∈ E ( D ) QR\in E(D) QR ∈ E ( D ) □ \square □
We do the following discharging. At the start, each v ∈ V ( G ) v\in V(G) v ∈ V ( G ) c h ( v ) = 0 ch(v)=0 c h ( v ) = 0 e ∈ E ( G ) e\in E(G) e ∈ E ( G ) c h ( e ) = 1 ch(e)=1 c h ( e ) = 1 ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = ∣ E ( G ) ∣ ≤ 5 s \sum_{x\in V(G)\cup E(G)}ch(x)=|E(G)|\le5s ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = ∣ E ( G ) ∣ ≤ 5 s
Step 1. Every edge x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x ∈ S x\in S x ∈ S y ∉ S y\notin S y ∈ / S x x x
Step 2. Every edge x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x , y ∈ S x,y\in S x , y ∈ S 1 / 2 1/2 1/2 x x x 1 / 2 1/2 1/2 y y y
Step 3. Every edge x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x ∈ P ∪ Q x\in P\cup Q x ∈ P ∪ Q y ∈ R y\in R y ∈ R x x x
Step 4. Every edge x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x , y ∈ P ∪ Q x,y\in P\cup Q x , y ∈ P ∪ Q 1 / 2 1/2 1/2 x x x 1 / 2 1/2 1/2 y y y
Step 5. Every vertex v v v P ∪ Q ∪ R P\cup Q\cup R P ∪ Q ∪ R S S S
Let the charge of each x ∈ V ( G ) ∪ E ( G ) x\in V(G)\cup E(G) x ∈ V ( G ) ∪ E ( G ) j j j c h j ( x ) ch_j(x) c h j ( x ) c h 4 ( e ) = 0 ch_4(e)=0 c h 4 ( e ) = 0 e ∈ E ( G ) e\in E(G) e ∈ E ( G ) c h 5 ( v ) ≥ 0 ch_5(v)\ge0 c h 5 ( v ) ≥ 0 v ∈ P ∪ Q ∪ R v\in P\cup Q\cup R v ∈ P ∪ Q ∪ R
e ( G ) ≥ ∑ v ∈ S c h 5 ( v ) . (18) e(G)\ge\sum_{v\in S}ch_5(v). \tag*{(18)} e ( G ) ≥ v ∈ S ∑ c h 5 ( v ) . (18) We claim that
(i) c h 5 ( v ) = 5 and d S ( v ) = 1 for each v ∈ S ; and (ii) The solo neighbors of v in P , Q are also solo neighbors of its neighbor in S . (19) \begin{aligned}
\text{(i)}\quad&ch_5(v)=5\text{ and }d_S(v)=1\text{ for each }v\in S;\text{ and}\\
\text{(ii)}\quad&\text{The solo neighbors of }v\text{ in }P,Q\text{ are also solo neighbors of its neighbor in }S. \tag*{(19)}
\end{aligned} (i) (ii) c h 5 ( v ) = 5 and d S ( v ) = 1 for each v ∈ S ; and The solo neighbors of v in P , Q are also solo neighbors of its neighbor in S . (19) By Claim 4.1, d ( v ) ≤ 4 d(v)\le4 d ( v ) ≤ 4 v ∈ S v\in S v ∈ S v ∈ S v\in S v ∈ S V ′ ∈ A V'\in\mathcal{A} V ′ ∈ A d S ( v ) = 0 d_S(v)=0 d S ( v ) = 0 v v v S S S v v v x x x P ∪ Q P\cup Q P ∪ Q d ( v ) ≤ 4 d(v)\le4 d ( v ) ≤ 4 x ≥ 1 x\ge1 x ≥ 1 c h 1 ( v ) ≥ x + ( 2 − x ) ⋅ 2 + 1 ch_1(v)\ge x+(2-x)\cdot2+1 c h 1 ( v ) ≥ x + ( 2 − x ) ⋅ 2 + 1 u ∈ P u\in P u ∈ P u ∈ Q u\in Q u ∈ Q v v v u u u { Q , R } \{Q,R\} { Q , R } { P , R } \{P,R\} { P , R } c h 4 ( u ) ≥ 1 2 + 1 = 3 2 ch_4(u)\ge\frac{1}{2}+1=\frac{3}{2} c h 4 ( u ) ≥ 2 1 + 1 = 2 3 v v v c h 5 ( v ) ≥ x ⋅ ( 1 + 3 2 ) + ( 2 − x ) ⋅ 2 + 1 = 5 + x 2 > 5 ch_5(v)\ge x\cdot\left(1+\frac{3}{2}\right)+(2-x)\cdot2+1=5+\frac{x}{2}>5 c h 5 ( v ) ≥ x ⋅ ( 1 + 2 3 ) + ( 2 − x ) ⋅ 2 + 1 = 5 + 2 x > 5
If d S ( v ) = 1 d_S(v)=1 d S ( v ) = 1 N S ( v ) = { v ′ } N_S(v)=\{v'\} N S ( v ) = { v ′ } N P ( v ) = { u 1 } N_P(v)=\{u_1\} N P ( v ) = { u 1 } N Q ( v ) = { u 2 } N_Q(v)=\{u_2\} N Q ( v ) = { u 2 } N R ( v ) = { u 3 } N_R(v)=\{u_3\} N R ( v ) = { u 3 } c h 2 ( v ) = 3 + 1 2 ch_2(v)=3+\frac{1}{2} c h 2 ( v ) = 3 + 2 1 c h 4 ( u i ) ≥ 1 2 + 1 = 3 2 ch_4(u_i)\ge\frac{1}{2}+1=\frac{3}{2} c h 4 ( u i ) ≥ 2 1 + 1 = 2 3 1 ≤ i ≤ 2 1\le i\le2 1 ≤ i ≤ 2 u i u_i u i 1 ≤ i ≤ 2 1\le i\le2 1 ≤ i ≤ 2 v v v v ′ v' v ′ u i u_i u i 1 ≤ i ≤ 2 1\le i\le2 1 ≤ i ≤ 2 v v v c h 5 ( v ) ≥ 3 + 1 2 + 2 ⋅ 1 2 ⋅ 3 2 = 5 ch_5(v)\ge3+\frac{1}{2}+2\cdot\frac{1}{2}\cdot\frac{3}{2}=5 c h 5 ( v ) ≥ 3 + 2 1 + 2 ⋅ 2 1 ⋅ 2 3 = 5 c h 5 ( v ) = 5 ch_5(v)=5 c h 5 ( v ) = 5 u 1 , u 2 u_1,u_2 u 1 , u 2 v v v v ′ v' v ′
By (5.2) and above discussion, e ( G ) ≥ ∑ v ∈ S c h 5 ( v ) ≥ 5 s ′ ≥ 5 s e(G)\ge\sum_{v\in S}ch_5(v)\ge5s'\ge5s e ( G ) ≥ ∑ v ∈ S c h 5 ( v ) ≥ 5 s ′ ≥ 5 s s ′ = s s'=s s ′ = s d S ( v ) = 1 d_S(v)=1 d S ( v ) = 1 v ∈ S v\in S v ∈ S e ( G ) ≤ 5 s e(G)\le5s e ( G ) ≤ 5 s
s is divisible by 2 and G [ S ] = s 2 K 2 . (20) s\text{ is divisible by }2\text{ and }G[S]=\frac{s}{2}K_2. \tag*{(20)} s is divisible by 2 and G [ S ] = 2 s K 2 . (20) For v ∈ S v\in S v ∈ S N S ( v ) = { v ′ } N_S(v)=\{v'\} N S ( v ) = { v ′ } N P ( v ) = { u p } N_P(v)=\{u_p\} N P ( v ) = { u p } N Q ( v ) = { u q } N_Q(v)=\{u_q\} N Q ( v ) = { u q } N P ( v ′ ) = { u p } N_P(v')=\{u_p\} N P ( v ′ ) = { u p } N Q ( v ′ ) = { u q } N_Q(v')=\{u_q\} N Q ( v ′ ) = { u q } u p u q ∉ E ( G ) u_pu_q\notin E(G) u p u q ∈ / E ( G ) d ( u p ) ≤ 4 d(u_p)\le4 d ( u p ) ≤ 4 N Q ( u p ) = { u q ′ } N_Q(u_p)=\{u'_q\} N Q ( u p ) = { u q ′ } u q ′ ≠ u q u'_q\ne u_q u q ′ = u q v ′ v' v ′ u p u_p u p N Q ( v ) ≠ N Q ( u p ) N_Q(v)\ne N_Q(u_p) N Q ( v ) = N Q ( u p )
G [ { v , v ′ , u p , u q } ] = K 4 . G[\{v,v',u_p,u_q\}]=K_4. G [{ v , v ′ , u p , u q }] = K 4 . Note that each x ∈ { v , v ′ , u p , u q } x\in\{v,v',u_p,u_q\} x ∈ { v , v ′ , u p , u q } R R R s ≤ 2 r − 2 s\le2r-2 s ≤ 2 r − 2 G [ S ∪ P ∪ Q ] G[S\cup P\cup Q] G [ S ∪ P ∪ Q ] K 4 K_4 K 4 K 1 K_1 K 1 K 1 K_1 K 1 G G G
For each K 4 , its neighbors in R are disjoint from the neighbors in R of every other K 4 . (21) \text{For each }K_4,\text{ its neighbors in }R\text{ are disjoint from the neighbors in }R\text{ of every other }K_4. \tag*{(21)} For each K 4 , its neighbors in R are disjoint from the neighbors in R of every other K 4 . (21) Indeed, if (21) does not hold, then we could rearrange the vertices of the K 4 K_4 K 4 S S S
If ∣ N R ( { v , v ′ , u p , u q } ) ∣ ≥ 2 |N_R(\{v,v',u_p,u_q\})| \ge2 ∣ N R ({ v , v ′ , u p , u q }) ∣ ≥ 2 u r , u r ′ ∈ N R ( { v , v ′ , u p , u q } ) u_r,u'_r \in N_R(\{v,v',u_p,u_q\}) u r , u r ′ ∈ N R ({ v , v ′ , u p , u q }) d ( u r ) d(u_r) d ( u r ) d ( u r ′ ) d(u'_r) d ( u r ′ ) u r u p , u r ′ u p ′ ∉ E ( G ) u_ru_p,u'_ru'_p \notin E(G) u r u p , u r ′ u p ′ ∈ / E ( G ) u p 0 ∈ P u^0_p \in P u p 0 ∈ P v ′ , u p 0 v',u^0_p v ′ , u p 0 R R R u r u_r u r P P P P − u p 0 + u r P-u^0_p+u_r P − u p 0 + u r ( R − u r ) ∪ { v ′ , u p 0 } (R-u_r)\cup\{v',u^0_p\} ( R − u r ) ∪ { v ′ , u p 0 } ∣ N R ( { v , v ′ , u p , u q } ) ∣ = 1 |N_R(\{v,v',u_p,u_q\})|=1 ∣ N R ({ v , v ′ , u p , u q }) ∣ = 1 (20) and (21) , G = s 2 K 5 ∪ ( n − 5 s 2 ) K 1 G=\frac{s}{2}K_5\cup(n-\frac{5s}{2})K_1 G = 2 s K 5 ∪ ( n − 2 5 s ) K 1 G G G
Case of ∣ B ∣ = 2 |B|=2 ∣ B ∣ = 2
In this section A = { X , R } \mathcal{A}=\{X,R\} A = { X , R } B = { S , Y } \mathcal{B}=\{S,Y\} B = { S , Y } { X , Y } = { P , Q } \{X,Y\}=\{P,Q\} { X , Y } = { P , Q } y = ∣ Y ∣ y=|Y| y = ∣ Y ∣ y ∈ { p , q } y\in\{p,q\} y ∈ { p , q } y ≥ r > r ′ y\ge r>r' y ≥ r > r ′ B = ⋃ W ∈ B W B=\bigcup_{W\in\mathcal{B}}W B = ⋃ W ∈ B W v ∈ B v\in B v ∈ B V ′ ∈ A V'\in\mathcal{A} V ′ ∈ A u ∈ S u\in S u ∈ S
d G [ B ] ( u ) = d G ( u ) − ∣ N X ∪ R ( u ) ∣ ≤ 2. d_{G[B]}(u)=d_G(u)-|N_{X\cup R}(u)|\le2. d G [ B ] ( u ) = d G ( u ) − ∣ N X ∪ R ( u ) ∣ ≤ 2. If G [ B ] G[B] G [ B ] K ‾ ∣ Y ∣ \overline{K}_{|Y|} K ∣ Y ∣ K ‾ r \overline{K}_r K r X X X K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r G G G e ( G [ B ] ) ≥ 3 ( s ′ − r ′ ) e(G[B])\ge3(s'-r') e ( G [ B ]) ≥ 3 ( s ′ − r ′ )
Let B ′ \mathcal{B}' B ′ B \mathcal{B} B S S S B ′ = ⋃ W ∈ B ′ W B'=\bigcup_{W\in\mathcal{B}'}W B ′ = ⋃ W ∈ B ′ W S Y ∈ E ( D ) SY\in E(D) S Y ∈ E ( D ) B ′ = ∅ B'=\varnothing B ′ = ∅ B ′ = Y B'=Y B ′ = Y X X X X R ∈ E ( D ) XR\in E(D) X R ∈ E ( D )
Claim 6.1. If v ∈ X v\in X v ∈ X u ∈ B ∖ B ′ u\in B\setminus B' u ∈ B ∖ B ′ N R ( v ) ≠ ∅ N_R(v)\ne\varnothing N R ( v ) = ∅
Proof. If u ∈ S u\in S u ∈ S v v v R R R u u u X X X r ′ r' r ′ u ∈ Y u\in Y u ∈ Y S Y ∈ E ( D ) SY\in E(D) S Y ∈ E ( D ) w ∈ S w\in S w ∈ S S Y SY S Y w w w Y Y Y u u u X X X v v v R R R r ′ r' r ′ □ \square □
Claim 6.2. No vertex v ∈ X v\in X v ∈ X B ∖ B ′ B\setminus B' B ∖ B ′
Proof. Suppose that some v ∈ X v\in X v ∈ X u , w ∈ B ∖ B ′ u,w\in B\setminus B' u , w ∈ B ∖ B ′ Claim 6.1 , v v v R R R v ′ ∈ X ∖ { v } v'\in X\setminus\{v\} v ′ ∈ X ∖ { v } R R R
If at least one of u , w u,w u , w S S S u ∈ S u\in S u ∈ S u u u v v v w w w X X X X X X w w w ∣ B ∣ |B| ∣ B ∣ u , w u,w u , w Y Y Y Y Y Y S S S s 0 ∈ S s_0\in S s 0 ∈ S Y Y Y s 0 s_0 s 0 Y Y Y u u u X X X v v v S S S w w w X X X Y Y Y □ \square □
Case 1: ∣ B ′ ∣ = 0 |B'|=0 ∣ B ′ ∣ = 0 We first show that e ( Y , X ) + e ( X , R ) ≥ 2 y e(Y,X)+e(X,R)\ge2y e ( Y , X ) + e ( X , R ) ≥ 2 y Y 1 = { v ∈ Y : ∣ N X ( v ) ∣ = 1 } Y_1=\{v\in Y:|N_X(v)|=1\} Y 1 = { v ∈ Y : ∣ N X ( v ) ∣ = 1 } x ∈ X x\in X x ∈ X Y x = { v ∈ Y 1 : N X ( v ) = { x } } Y_x=\{v\in Y_1:N_X(v)=\{x\}\} Y x = { v ∈ Y 1 : N X ( v ) = { x }} Claim 6.2 and the facts that Y Y Y Y ⊆ B ∖ B ′ Y\subseteq B\setminus B' Y ⊆ B ∖ B ′ Y x Y_x Y x Claim 6.1 , whenever Y x ≠ ∅ Y_x\ne\varnothing Y x = ∅ x x x R R R Y ∖ Y 1 Y\setminus Y_1 Y ∖ Y 1 X X X Y 1 Y_1 Y 1 X X X X X X R R R e ( Y , X ) + e ( X , R ) ≥ 2 y e(Y,X)+e(X,R)\ge2y e ( Y , X ) + e ( X , R ) ≥ 2 y
Also, every vertex of Y Y Y R R R e ( Y , R ) ≥ y e(Y,R) \ge y e ( Y , R ) ≥ y S S S X X X R R R e ( S , X ∪ R ) ≥ 2 s ′ e(S,X \cup R) \ge2s' e ( S , X ∪ R ) ≥ 2 s ′ e ( G [ B ] ) ≥ 3 ( s ′ − r ′ ) e(G[B]) \ge3(s' - r') e ( G [ B ]) ≥ 3 ( s ′ − r ′ )
Then we obtain
e ( G ) ≥ e ( G [ B ] ) + e ( S , X ∪ R ) + e ( Y , X ) + e ( Y , R ) + e ( X , R ) ≥ 3 ( s ′ − r ′ ) + 2 s ′ + 2 y + y = 5 s ′ + 3 y − 3 r ′ > 5 s , \begin{aligned}
e(G) &\ge e(G[B]) + e(S,X \cup R) + e(Y,X) + e(Y,R) + e(X,R)\\
&\ge3(s' - r') + 2s' + 2y + y\\
&= 5s' + 3y - 3r' > 5s,
\end{aligned} e ( G ) ≥ e ( G [ B ]) + e ( S , X ∪ R ) + e ( Y , X ) + e ( Y , R ) + e ( X , R ) ≥ 3 ( s ′ − r ′ ) + 2 s ′ + 2 y + y = 5 s ′ + 3 y − 3 r ′ > 5 s , where the last inequality follows from s ′ ≥ s s' \ge s s ′ ≥ s y ≥ r > r ′ y \ge r > r' y ≥ r > r ′ e ( G ) ≤ 5 s e(G) \le5s e ( G ) ≤ 5 s
Case 2: B ′ = { Y } B' = \{Y\} B ′ = { Y } B ∖ B ′ = S B \setminus B' = S B ∖ B ′ = S Y Y Y S S S S S S Y Y Y e ( S , Y ) ≥ s ′ e(S,Y) \ge s' e ( S , Y ) ≥ s ′ S S S R R R Y Y Y X X X R R R
Now we show that e ( S , X ) + e ( X , R ) ≥ 3 s ′ 2 e(S,X) + e(X,R) \ge\frac{3s'}{2} e ( S , X ) + e ( X , R ) ≥ 2 3 s ′ S 1 = { v ∈ S : ∣ N X ( v ) ∣ = 1 } S_1 = \{v \in S : |N_X(v)| = 1\} S 1 = { v ∈ S : ∣ N X ( v ) ∣ = 1 } x ∈ X x \in X x ∈ X S x = { v ∈ S 1 : N X ( v ) = { x } } S_x = \{v \in S_1 : N_X(v) = \{x\}\} S x = { v ∈ S 1 : N X ( v ) = { x }} S x S_x S x G [ S ] G[S] G [ S ] Y Y Y S S S Δ ( G [ S ] ) ≤ 1 \Delta(G[S]) \le1 Δ ( G [ S ]) ≤ 1 ∣ S x ∣ ≤ 2 |S_x| \le2 ∣ S x ∣ ≤ 2 S x S_x S x x x x R R R k = ∣ S 1 ∣ k = |S_1| k = ∣ S 1 ∣
e ( S , X ) + e ( X , R ) ≥ 2 ( s ′ − k ) + k + ⌈ k 2 ⌉ ≥ 3 s ′ 2 , e(S,X) + e(X,R) \ge2(s' - k) + k + \left\lceil\frac{k}{2}\right\rceil\ge\frac{3s'}{2}, e ( S , X ) + e ( X , R ) ≥ 2 ( s ′ − k ) + k + ⌈ 2 k ⌉ ≥ 2 3 s ′ , as desired.
Since Δ ( G [ S ] ) ≤ 1 \Delta(G[S]) \le1 Δ ( G [ S ]) ≤ 1 α ( G [ S ] ) ≤ r − 1 \alpha(G[S]) \le r - 1 α ( G [ S ]) ≤ r − 1 s ′ ≤ 2 r − 2 s' \le2r - 2 s ′ ≤ 2 r − 2
e ( G [ S ] ) ≥ t ‾ s ′ , r − 1 = { 0 , if 0 ≤ s ′ ≤ r − 1 , s ′ − r + 1 , if r ≤ s ′ ≤ 2 r − 2. e(G[S]) \ge\overline{t}_{s',r-1} =
\begin{cases}
0, & \text{if } 0 \le s' \le r - 1,\\
s' - r + 1, & \text{if } r \le s' \le2r - 2.
\end{cases} e ( G [ S ]) ≥ t s ′ , r − 1 = { 0 , s ′ − r + 1 , if 0 ≤ s ′ ≤ r − 1 , if r ≤ s ′ ≤ 2 r − 2. Now we have that
e ( G ) ≥ e ( G [ S ] ) + e ( S , X ∪ Y ∪ R ) + e ( X , R ) + e ( Y , X ∪ R ) ≥ t ‾ s ′ , r − 1 + 7 s ′ 2 + 2 y . \begin{aligned}
e(G) \ge e(G[S]) + e(S,X \cup Y \cup R) + e(X,R) + e(Y,X \cup R) \\
&\ge\overline{t}_{s',r-1} + \frac{7s'}{2} + 2y.
\end{aligned} e ( G ) ≥ e ( G [ S ]) + e ( S , X ∪ Y ∪ R ) + e ( X , R ) + e ( Y , X ∪ R ) ≥ t s ′ , r − 1 + 2 7 s ′ + 2 y . If s ′ ≤ r − 1 s' \le r - 1 s ′ ≤ r − 1 y ≥ r ≥ s ′ + 1 y \ge r \ge s' + 1 y ≥ r ≥ s ′ + 1
t ‾ s ′ , r − 1 + 7 s ′ 2 + 2 y ≥ 7 s ′ 2 + 2 ( s ′ + 1 ) > 5 s ′ ≥ 5 s . \overline{t}_{s',r-1} + \frac{7s'}{2} + 2y \ge\frac{7s'}{2} + 2(s' + 1) > 5s' \ge5s. t s ′ , r − 1 + 2 7 s ′ + 2 y ≥ 2 7 s ′ + 2 ( s ′ + 1 ) > 5 s ′ ≥ 5 s . If r ≤ s ′ ≤ 2 r − 2 r \le s' \le2r - 2 r ≤ s ′ ≤ 2 r − 2
t ‾ s ′ , r − 1 + 7 s ′ 2 + 2 y ≥ s ′ − r + 1 + 7 s ′ 2 + 2 r = 9 s ′ 2 + r + 1 > 5 s ′ ≥ 5 s , \overline{t}_{s',r-1} + \frac{7s'}{2} + 2y \ge s' - r + 1 + \frac{7s'}{2} + 2r = \frac{9s'}{2} + r + 1 > 5s' \ge5s, t s ′ , r − 1 + 2 7 s ′ + 2 y ≥ s ′ − r + 1 + 2 7 s ′ + 2 r = 2 9 s ′ + r + 1 > 5 s ′ ≥ 5 s , In both cases e ( G ) > 5 s e(G) > 5s e ( G ) > 5 s e ( G ) ≤ 5 s e(G) \le5s e ( G ) ≤ 5 s
Case of ∣ B ∣ = 3 |B| = 3 ∣ B ∣ = 3
In this section, ∣ B ∣ = 3 |B| = 3 ∣ B ∣ = 3 B = { P , Q , S } B = \{P,Q,S\} B = { P , Q , S } x ∈ S ∪ P ∪ Q x \in S \cup P \cup Q x ∈ S ∪ P ∪ Q R R R
∣ E ( S ∪ P ∪ Q , R ) ∣ ≥ s ′ + p + q , (22) |E(S \cup P \cup Q,R)| \ge s' + p + q, \tag*{(22)} ∣ E ( S ∪ P ∪ Q , R ) ∣ ≥ s ′ + p + q , (22) and by Claim 4.1, s ′ + p + q ≤ 4 r ′ s' + p + q \le4r' s ′ + p + q ≤ 4 r ′ p , q ≥ r ≥ r ′ + 1 p,q \ge r \ge r' + 1 p , q ≥ r ≥ r ′ + 1
s ≤ s ′ ≤ 4 r ′ − p − q ≤ 2 r ′ − 2 ≤ 2 ( r − 2 ) . (23) s \le s' \le4r' - p - q \le2r' - 2 \le2(r - 2). \tag*{(23)} s ≤ s ′ ≤ 4 r ′ − p − q ≤ 2 r ′ − 2 ≤ 2 ( r − 2 ) . (23) Let B ′ B' B ′ B \mathcal{B} B S S S ( P , Q , R ) (P,Q,R) ( P , Q , R )
(N5) ∣ B ′ ∣ |B'| ∣ B ′ ∣ minimum .
Since S S S
Case 1: B ′ = ∅ B'=\emptyset B ′ = ∅ ( P , Q , R ) (P,Q,R) ( P , Q , R )
(N6) ∑ y ∈ R d ( y ) \sum_{y\in R}d(y) ∑ y ∈ R d ( y ) minimum .
Similarly to (3.6) (and with a similar proof) we now show
(7.3) If x ∈ S ∪ P ∪ Q x\in S\cup P\cup Q x ∈ S ∪ P ∪ Q y y y R R R d ( x ) ≥ d ( y ) d(x)\ge d(y) d ( x ) ≥ d ( y )
Indeed, if d ( x ) < d ( y ) d(x)<d(y) d ( x ) < d ( y ) x x x R R R y y y S S S x x x S S S x ∈ Q x\in Q x ∈ Q S , Q S,Q S , Q D D D ∑ y ∈ R d ( y ) \sum_{y\in R}d(y) ∑ y ∈ R d ( y )
We do the following discharging. At the start, the charge c h ( x ) ch(x) c h ( x ) x ∈ S ∪ P ∪ Q x\in S\cup P\cup Q x ∈ S ∪ P ∪ Q x ∈ R ∪ E ( G ) x\in R\cup E(G) x ∈ R ∪ E ( G ) ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = s ′ + p + q \sum_{x\in V(G)\cup E(G)}ch(x)=s'+p+q ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = s ′ + p + q
Step 1: each edge u v ∈ E ( G [ S ∪ P ∪ Q ] ) uv\in E(G[S\cup P\cup Q]) uv ∈ E ( G [ S ∪ P ∪ Q ]) 1 / 6 1/6 1/6
Step 2: each u ∈ S ∪ P ∪ Q u\in S\cup P\cup Q u ∈ S ∪ P ∪ Q R R R
Let c h ∗ ( x ) ch^*(x) c h ∗ ( x ) x ∈ V ( G ) ∪ E ( G ) x\in V(G)\cup E(G) x ∈ V ( G ) ∪ E ( G )
(7.4) c h ∗ ( v ) ≤ 2 ch^*(v)\le2 c h ∗ ( v ) ≤ 2 v ∈ R v\in R v ∈ R
Indeed, if d ( v ) ≤ 2 d(v)\le2 d ( v ) ≤ 2 d ( v ) = 3 d(v)=3 d ( v ) = 3 u v ∈ E ( G ) uv\in E(G) uv ∈ E ( G ) v v v u u u u u u v v v 1 / 2 1/2 1/2 v v v u u u u u u 2 ( 1 / 6 ) 2(1/6) 2 ( 1/6 ) v v v 1 − 1 / 3 = 2 / 3 1-1/3=2/3 1 − 1/3 = 2/3 v v v 3 ( 2 / 3 ) = 2 3(2/3)=2 3 ( 2/3 ) = 2
Suppose now that d ( v ) = 4 d(v)=4 d ( v ) = 4 v v v u u u u u u v v v d ( u ) ≥ 4 d(u)\ge4 d ( u ) ≥ 4 u u u 3 ( 1 / 6 ) = 1 / 2 3(1/6)=1/2 3 ( 1/6 ) = 1/2 1 − 1 / 2 = 1 / 2 1-1/2=1/2 1 − 1/2 = 1/2 v v v 4 ( 1 / 2 ) = 2 4(1/2)=2 4 ( 1/2 ) = 2
So, by the discharging rules and (7.4), s ′ + p + q ≤ 1 3 ∣ E ( G [ S ∪ P ∪ Q ] ) ∣ + 2 r ′ s'+p+q\le\frac{1}{3}|E(G[S\cup P\cup Q])|+2r' s ′ + p + q ≤ 3 1 ∣ E ( G [ S ∪ P ∪ Q ]) ∣ + 2 r ′
e ( G [ S ∪ P ∪ Q ] ) ≥ 3 ( s ′ + p + q − 2 r ′ ) ≥ 3 ( s + 2 ) e(G[S\cup P\cup Q])\ge3(s'+p+q-2r')\ge3(s+2) e ( G [ S ∪ P ∪ Q ]) ≥ 3 ( s ′ + p + q − 2 r ′ ) ≥ 3 ( s + 2 )
e ( G ) ≥ 3 ( s + 1 ) + ( s ′ + p + q ) ≥ 4 s + 3 + 2 r ≥ 5 s + 5 e(G)\ge3(s+1)+(s'+p+q)\ge4s+3+2r\ge5s+5 e ( G ) ≥ 3 ( s + 1 ) + ( s ′ + p + q ) ≥ 4 s + 3 + 2 r ≥ 5 s + 5
a contradiction.
Case 2: ∣ B ′ ∣ = 1 |B'|=1 ∣ B ′ ∣ = 1 P P P Q Q Q B ′ = { Q } B'=\{Q\} B ′ = { Q } e ( S ∪ P , Q ∪ R ) + e ( Q , R ) ≥ 2 ( s ′ + p ) + q e(S\cup P,Q\cup R)+e(Q,R)\ge2(s'+p)+q e ( S ∪ P , Q ∪ R ) + e ( Q , R ) ≥ 2 ( s ′ + p ) + q e ( G [ S ∪ P ] ) ≥ 3 ( s ′ − r ′ ) e(G[S\cup P])\ge3(s'-r') e ( G [ S ∪ P ]) ≥ 3 ( s ′ − r ′ ) e ( G ) ≥ 2 ( s ′ + p ) + q + 3 ( s ′ − r ′ ) ≥ 5 s ′ + 3 e(G)\ge2(s'+p)+q+3(s'-r')\ge5s'+3 e ( G ) ≥ 2 ( s ′ + p ) + q + 3 ( s ′ − r ′ ) ≥ 5 s ′ + 3
Case 3: ∣ B ′ ∣ = 2 |B'|=2 ∣ B ′ ∣ = 2 B ′ = { P , Q } B'=\{P,Q\} B ′ = { P , Q } S ′ = { v ∈ S : ∣ N ( v ) ∩ ( P ∪ Q ) ∣ = 2 } S'=\{v\in S:|N(v)\cap(P\cup Q)|=2\} S ′ = { v ∈ S : ∣ N ( v ) ∩ ( P ∪ Q ) ∣ = 2 } S ′ ′ = S ∖ S ′ S''=S\setminus S' S ′′ = S ∖ S ′
Claim 7.1. No vertex in P ∪ Q P\cup Q P ∪ Q S S S
Proof. Suppose v ∈ P v\in P v ∈ P u , u ′ ∈ S u,u'\in S u , u ′ ∈ S u u u P P P v v v S S S u ′ u' u ′ P − v + u P-v+u P − v + u
Claim 7.2. e ( G [ S ∪ P ∪ Q ] ) ≥ 3 s ′ − 1 e(G[S\cup P\cup Q])\ge3s'-1 e ( G [ S ∪ P ∪ Q ]) ≥ 3 s ′ − 1 Proof. First, we show that
If P has two vertices x , x ′ movable to Q , then each y ∈ Q that is a unique neighbor of some z ∈ S ′ is not movable to P . (24) \text{If } P \text{ has two vertices } x,x' \text{ movable to } Q,\text{ then each } y\in Q \text{ that is a unique neighbor of some } z\in S' \text{ is not movable to } P. \tag*{(24)} If P has two vertices x , x ′ movable to Q , then each y ∈ Q that is a unique neighbor of some z ∈ S ′ is not movable to P . (24) Indeed, if such y ∈ Q y\in Q y ∈ Q z ∈ S ′ z\in S' z ∈ S ′ N ( z ) ∩ ( P ∪ Q ) = { y , y ′ } N(z)\cap(P\cup Q)=\{y,y'\} N ( z ) ∩ ( P ∪ Q ) = { y , y ′ } y ′ ∈ P y'\in P y ′ ∈ P y ′ ≠ x ′ y'\ne x' y ′ = x ′ y y y P P P x ′ x' x ′ Q − y Q-y Q − y z z z Q − y + x ′ Q-y+x' Q − y + x ′
By (7.5) and the symmetry between P P P Q Q Q
for some y ∈ Q , each unique neighbor of a z ∈ S ′ in Q − y has a neighbor in P . (25) \text{for some } y\in Q,\text{ each unique neighbor of a } z\in S' \text{ in } Q-y \text{ has a neighbor in } P. \tag*{(25)} for some y ∈ Q , each unique neighbor of a z ∈ S ′ in Q − y has a neighbor in P . (25) We fix y ∈ Q y\in Q y ∈ Q c h ( x ) ch(x) c h ( x ) x ∈ E ( G [ S ∪ P ∪ Q ] ) ∪ { y } x\in E(G[S\cup P\cup Q])\cup\{y\} x ∈ E ( G [ S ∪ P ∪ Q ]) ∪ { y } x ∈ ( S ∪ P ∪ Q ) ∖ { y } x\in(S\cup P\cup Q)\setminus\{y\} x ∈ ( S ∪ P ∪ Q ) ∖ { y } ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = e ( G [ S ∪ P ∪ Q ] ) + 1 \sum_{x\in V(G)\cup E(G)}ch(x)=e(G[S\cup P\cup Q])+1 ∑ x ∈ V ( G ) ∪ E ( G ) c h ( x ) = e ( G [ S ∪ P ∪ Q ]) + 1
Step 1: each edge u v ∈ E ( S , P ∪ Q ) uv\in E(S,P\cup Q) uv ∈ E ( S , P ∪ Q ) S S S
Step 2: each edge u v ∈ E ( P , Q ) uv\in E(P,Q) uv ∈ E ( P , Q ) Q Q Q
Step 3: each edge u v ∈ E ( G [ S ] ) uv\in E(G[S]) uv ∈ E ( G [ S ]) 1 / 2 1/2 1/2
Step 4: each u ∈ Q u\in Q u ∈ Q S S S u u u Q Q Q
Let c h i ( x ) ch_i(x) c h i ( x ) x ∈ V ( G ) ∪ E ( G ) x\in V(G)\cup E(G) x ∈ V ( G ) ∪ E ( G ) i i i c h 4 ( x ) ≥ 0 ch_4(x)\ge0 c h 4 ( x ) ≥ 0 x ∈ E ( G [ S ∪ P ∪ Q ] ) ∪ P ∪ Q x\in E(G[S\cup P\cup Q])\cup P\cup Q x ∈ E ( G [ S ∪ P ∪ Q ]) ∪ P ∪ Q ∑ v ∈ S c h 4 ( v ) ≤ e ( G [ S ∪ P ∪ Q ] ) + 1 \sum_{v\in S}ch_4(v)\le e(G[S\cup P\cup Q])+1 ∑ v ∈ S c h 4 ( v ) ≤ e ( G [ S ∪ P ∪ Q ]) + 1
c h 4 ( v ) ≥ 3 for every v ∈ S . (26) ch_4(v)\ge3\text{ for every }v\in S. \tag*{(26)} c h 4 ( v ) ≥ 3 for every v ∈ S . (26) Indeed, if v ∈ S ′ ′ v\in S'' v ∈ S ′′ c h 2 ( v ) ≥ 3 ch_2(v)\ge3 c h 2 ( v ) ≥ 3 v ∈ S ′ v\in S' v ∈ S ′ v ′ v' v ′ v v v Q Q Q v v v S S S Claim 7.1 , v v v v ′ v' v ′ c h 4 ( v ) ≥ 2 + 1 = 3 ch_4(v)\ge2+1=3 c h 4 ( v ) ≥ 2 + 1 = 3 v v v S S S d ( v ) ≤ 4 d(v)\le4 d ( v ) ≤ 4 v ′ ′ v'' v ′′ v v v 1 / 2 1/2 1/2 v ′ v' v ′ 1 / 2 1/2 1/2 v v ′ ′ vv'' v v ′′
Since (7.7) implies e ( G [ S ∪ P ∪ Q ] ) ≥ 3 s ′ − 1 e(G[S\cup P\cup Q])\ge3s'-1 e ( G [ S ∪ P ∪ Q ]) ≥ 3 s ′ − 1
Now by Claim 7.2, (7.1) and (7.2),
e ( G ) ≥ ( 3 s ′ − 1 ) + ( s ′ + p + q ) = 4 s ′ − 1 + p + q ≥ 4 s ′ + 1 + 2 r ′ > 5 s ′ e(G)\ge(3s'-1)+(s'+p+q)=4s'-1+p+q\ge4s'+1+2r'>5s' e ( G ) ≥ ( 3 s ′ − 1 ) + ( s ′ + p + q ) = 4 s ′ − 1 + p + q ≥ 4 s ′ + 1 + 2 r ′ > 5 s ′ This contradiction finishes the proof.
Helpful theorems
Theorem 9. [6 ] Every graph with maximum degree at most ℓ \ell ℓ ( ℓ + 1 ) (\ell+1) ( ℓ + 1 )
Theorem 10. Let 2 ≤ ℓ ≤ 3 2\le\ell\le3 2 ≤ ℓ ≤ 3 p 1 ≥ p 2 ≥ ⋯ ≥ p ℓ ≥ 2 p_1\ge p_2\ge\cdots\ge p_\ell\ge2 p 1 ≥ p 2 ≥ ⋯ ≥ p ℓ ≥ 2 c = max { i ∣ p i = p 1 , 1 ≤ i ≤ ℓ } − 1 c=\max\{i\mid p_i=p_1,\ 1\le i\le\ell\}-1 c = max { i ∣ p i = p 1 , 1 ≤ i ≤ ℓ } − 1
If there is an integer n 3 ≥ p 1 + p 2 + ⋯ + p ℓ n_3\ge p_1+p_2+\cdots+p_\ell n 3 ≥ p 1 + p 2 + ⋯ + p ℓ K c ∨ T n 3 − c , p 1 − 1 ∈ EX ( n 3 , K p 1 ∪ ⋯ ∪ K p ℓ ) K_c\vee T_{n_3-c,p_1-1}\in\operatorname{EX}(n_3,K_{p_1}\cup\cdots\cup K_{p_\ell}) K c ∨ T n 3 − c , p 1 − 1 ∈ EX ( n 3 , K p 1 ∪ ⋯ ∪ K p ℓ ) K c ∨ T n − c , p 1 − 1 ∈ EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) K_c\vee T_{n-c,p_1-1}\in\operatorname{EX}(n,K_{p_1}\cup\cdots\cup K_{p_\ell}) K c ∨ T n − c , p 1 − 1 ∈ EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) n ≥ n 3 n\ge n_3 n ≥ n 3
If there is an integer n 4 ≥ p 1 + p 2 + ⋯ + p ℓ n_4\ge p_1+p_2+\cdots+p_\ell n 4 ≥ p 1 + p 2 + ⋯ + p ℓ EX ( n 4 , K p 1 ∪ ⋯ ∪ K p ℓ ) = { K c ∨ T n 4 − c , p 1 − 1 } \operatorname{EX}(n_4,K_{p_1}\cup\cdots\cup K_{p_\ell})=\{K_c\vee T_{n_4-c,p_1-1}\} EX ( n 4 , K p 1 ∪ ⋯ ∪ K p ℓ ) = { K c ∨ T n 4 − c , p 1 − 1 } EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) = { K c ∨ T n − c , p 1 − 1 } \operatorname{EX}(n,K_{p_1}\cup\cdots\cup K_{p_\ell})=\{K_c\vee T_{n-c,p_1-1}\} EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) = { K c ∨ T n − c , p 1 − 1 } n ≥ n 4 n\ge n_4 n ≥ n 4
Proof. Note that n 3 ≤ n 4 n_3 \le n_4 n 3 ≤ n 4 n n n n 3 ≤ n ′ < n n_3 \le n' < n n 3 ≤ n ′ < n G ∈ EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) G \in\operatorname{EX}(n, K_{p_1} \cup\cdots\cup K_{p_\ell}) G ∈ EX ( n , K p 1 ∪ ⋯ ∪ K p ℓ ) G G G K p 1 K_{p_1} K p 1 c = 0 c=0 c = 0 G = T n , p 1 − 1 G=T_{n,p_1-1} G = T n , p 1 − 1 G G G K p 1 K_{p_1} K p 1
Claim 8.1. δ ( G ) ≤ n − 1 − ⌊ n − c − 1 p 1 − 1 ⌋ \delta(G) \le n-1-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor δ ( G ) ≤ n − 1 − ⌊ p 1 − 1 n − c − 1 ⌋
Proof. If δ ( G ) ≥ n − ⌊ n − c − 1 p 1 − 1 ⌋ \delta(G) \ge n-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor δ ( G ) ≥ n − ⌊ p 1 − 1 n − c − 1 ⌋ Δ ( G ‾ ) ≤ ⌊ n − c − 1 p 1 − 1 ⌋ − 1 \Delta(\overline{G}) \le\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor-1 Δ ( G ) ≤ ⌊ p 1 − 1 n − c − 1 ⌋ − 1
Case 1: n ≤ ℓ ( p 1 − 1 ) + c n \le\ell(p_1-1)+c n ≤ ℓ ( p 1 − 1 ) + c Δ ( G ‾ ) ≤ ℓ − 2 ≤ 1 \Delta(\overline{G}) \le\ell-2 \le1 Δ ( G ) ≤ ℓ − 2 ≤ 1 G ‾ = x 1 K 2 ∪ y 1 K 1 \overline{G}=x_1K_2\cup y_1K_1 G = x 1 K 2 ∪ y 1 K 1
For 1 ≤ k ≤ ℓ − 1 , if G ‾ contains disjoint induced K ‾ p 1 , … , K ‾ p k , then G ‾ contains disjoint induced K ‾ p 1 , … , K ‾ p k , K ‾ p k + 1 . (27) \text{For }1\le k\le\ell-1,\text{ if }\overline{G}\text{ contains disjoint induced }\overline{K}_{p_1},\ldots,\overline{K}_{p_k},\text{ then }\overline{G}\text{ contains}
\text{ disjoint induced }\overline{K}_{p_1},\ldots,\overline{K}_{p_k},\overline{K}_{p_{k+1}}. \tag*{(27)} For 1 ≤ k ≤ ℓ − 1 , if G contains disjoint induced K p 1 , … , K p k , then G contains disjoint induced K p 1 , … , K p k , K p k + 1 . (27) Take pairwise disjoint independent sets S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k ∣ S i ∣ = p i |S_i|=p_i ∣ S i ∣ = p i 1 ≤ i ≤ k 1\le i\le k 1 ≤ i ≤ k G ‾ \overline{G} G S 1 ∪ ⋯ ∪ S k S_1\cup\cdots\cup S_k S 1 ∪ ⋯ ∪ S k x 1 ≤ p 1 + ⋯ + p k x_1\le p_1+\cdots+p_k x 1 ≤ p 1 + ⋯ + p k α ( G ‾ − S 1 − ⋯ − S k ) = n − p 1 − ⋯ − p k ≥ p k + 1 \alpha(\overline{G}-S_1-\cdots-S_k)=n-p_1-\cdots-p_k\ge p_{k+1} α ( G − S 1 − ⋯ − S k ) = n − p 1 − ⋯ − p k ≥ p k + 1 x 1 > p 1 + ⋯ + p k x_1>p_1+\cdots+p_k x 1 > p 1 + ⋯ + p k α ( G ‾ − S 1 − ⋯ − S k ) ≥ p 1 + ⋯ + p k ≥ p k + 1 \alpha(\overline{G}-S_1-\cdots-S_k)\ge p_1+\cdots+p_k\ge p_{k+1} α ( G − S 1 − ⋯ − S k ) ≥ p 1 + ⋯ + p k ≥ p k + 1 α ( G ‾ − S 1 − ⋯ − S k ) ≥ p k + 1 \alpha(\overline{G}-S_1-\cdots-S_k)\ge p_{k+1} α ( G − S 1 − ⋯ − S k ) ≥ p k + 1 S k + 1 S_{k+1} S k + 1 p k + 1 p_{k+1} p k + 1 G ‾ \overline{G} G K ‾ p 1 , … , K ‾ p ℓ \overline{K}_{p_1},\ldots,\overline{K}_{p_\ell} K p 1 , … , K p ℓ G G G K p 1 ∪ ⋯ ∪ K p ℓ K_{p_1}\cup\cdots\cup K_{p_\ell} K p 1 ∪ ⋯ ∪ K p ℓ
Case 2: n ≥ ℓ ( p 1 − 1 ) + c + 1 n\ge\ell(p_1-1)+c+1 n ≥ ℓ ( p 1 − 1 ) + c + 1 ⌊ n − c − 1 p 1 − 1 ⌋ ≥ ℓ \left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor\ge\ell ⌊ p 1 − 1 n − c − 1 ⌋ ≥ ℓ G ‾ \overline{G} G V 1 , V 2 , … , V ⌊ n − c − 1 p 1 − 1 ⌋ V_1,V_2,\ldots,V_{\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor} V 1 , V 2 , … , V ⌊ p 1 − 1 n − c − 1 ⌋ ∣ V 1 ∣ ≥ ∣ V 2 ∣ ≥ ⋯ ≥ ∣ V ⌊ n − c − 1 p 1 − 1 ⌋ ∣ |V_1|\ge|V_2|\ge\cdots\ge\left|V_{\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor}\right| ∣ V 1 ∣ ≥ ∣ V 2 ∣ ≥ ⋯ ≥ V ⌊ p 1 − 1 n − c − 1 ⌋ G G G K p 1 ∪ ⋯ ∪ K p ℓ K_{p_1}\cup\cdots\cup K_{p_\ell} K p 1 ∪ ⋯ ∪ K p ℓ ∣ V c + 1 ∣ ≤ p 1 − 1 |V_{c+1}|\le p_1-1 ∣ V c + 1 ∣ ≤ p 1 − 1 ∣ V j ∣ ≤ p 1 |V_j|\le p_1 ∣ V j ∣ ≤ p 1 1 ≤ j ≤ c 1\le j\le c 1 ≤ j ≤ c ∣ V j ∣ ≤ p 1 − 1 |V_j|\le p_1-1 ∣ V j ∣ ≤ p 1 − 1 c + 1 ≤ j ≤ ⌊ n − c − 1 p 1 − 1 ⌋ c+1\le j\le\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor c + 1 ≤ j ≤ ⌊ p 1 − 1 n − c − 1 ⌋
n = ∑ j = 1 ⌊ n − c − 1 p 1 − 1 ⌋ ∣ V j ∣ ≤ c p 1 + ( ⌊ n − c − 1 p 1 − 1 ⌋ − c ) ( p 1 − 1 ) < n , n=\sum_{j=1}^{\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor}|V_j|
\le cp_1+\left(\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor-c\right)(p_1-1)<n, n = j = 1 ∑ ⌊ p 1 − 1 n − c − 1 ⌋ ∣ V j ∣ ≤ c p 1 + ( ⌊ p 1 − 1 n − c − 1 ⌋ − c ) ( p 1 − 1 ) < n , a contradiction. □
By Claim 8.1, there is a vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) d ( v ) = δ ( G ) ≤ n − 1 − ⌊ n − c − 1 p 1 − 1 ⌋ d(v)=\delta(G)\le n-1-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor d ( v ) = δ ( G ) ≤ n − 1 − ⌊ p 1 − 1 n − c − 1 ⌋ e ( G ) ≥ e ( K c ∨ T n − c , p 1 − 1 ) e(G)\ge e(K_c\vee T_{n-c,p_1-1}) e ( G ) ≥ e ( K c ∨ T n − c , p 1 − 1 )
e ( G ) = e ( G − v ) + d ( v ) ≤ e ( K c ∨ T n − c − 1 , p 1 − 1 ) + n − 1 − ⌊ n − c − 1 p 1 − 1 ⌋ = e ( K c ∨ T n − c , p 1 − 1 ) , e(G)=e(G-v)+d(v)\le e(K_c\vee T_{n-c-1,p_1-1})+n-1-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor=e(K_c\vee T_{n-c,p_1-1}), e ( G ) = e ( G − v ) + d ( v ) ≤ e ( K c ∨ T n − c − 1 , p 1 − 1 ) + n − 1 − ⌊ p 1 − 1 n − c − 1 ⌋ = e ( K c ∨ T n − c , p 1 − 1 ) , we conclude that e ( G ) = e ( K c ∨ T n − c , p 1 − 1 ) e(G)=e(K_c\vee T_{n-c,p_1-1}) e ( G ) = e ( K c ∨ T n − c , p 1 − 1 ) d ( v ) = n − 1 − ⌊ n − c − 1 p 1 − 1 ⌋ d(v)=n-1-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor d ( v ) = n − 1 − ⌊ p 1 − 1 n − c − 1 ⌋ e ( G − v ) = e ( K c ∨ T n − c − 1 , p 1 − 1 ) e(G-v)=e(K_c\vee T_{n-c-1,p_1-1}) e ( G − v ) = e ( K c ∨ T n − c − 1 , p 1 − 1 )
Suppose now that Part 2) holds for all n 4 ≤ n ′ < n n_4\le n'<n n 4 ≤ n ′ < n G − v = K c ∨ T n − c − 1 , p 1 − 1 G-v=K_c\vee T_{n-c-1,p_1-1} G − v = K c ∨ T n − c − 1 , p 1 − 1 V ( G ) − v V(G)-v V ( G ) − v p 1 p_1 p 1 V ′ , V 1 , V 2 , … , V p 1 − 1 V',V_1,V_2,\ldots,V_{p_1-1} V ′ , V 1 , V 2 , … , V p 1 − 1 G [ V ′ ] = K c G[V']=K_c G [ V ′ ] = K c V 1 , … , V p 1 − 1 V_1,\ldots,V_{p_1-1} V 1 , … , V p 1 − 1 ⌈ n − c − 1 p 1 − 1 ⌉ ≥ ∣ V 1 ∣ ≥ ∣ V 2 ∣ ≥ ⋯ ≥ ∣ V p 1 − 1 ∣ ≥ ⌊ n − c − 1 p 1 − 1 ⌋ \left\lceil\frac{n-c-1}{p_1-1}\right\rceil\ge|V_1|\ge|V_2|\ge\cdots\ge|V_{p_1-1}|\ge\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor ⌈ p 1 − 1 n − c − 1 ⌉ ≥ ∣ V 1 ∣ ≥ ∣ V 2 ∣ ≥ ⋯ ≥ ∣ V p 1 − 1 ∣ ≥ ⌊ p 1 − 1 n − c − 1 ⌋
If N ( v ) ∩ V j ≠ ∅ N(v)\cap V_j\ne\varnothing N ( v ) ∩ V j = ∅ 1 ≤ j ≤ p 1 − 1 1\le j\le p_1-1 1 ≤ j ≤ p 1 − 1 v j ∈ N ( v ) ∩ V j v_j\in N(v)\cap V_j v j ∈ N ( v ) ∩ V j U 1 = { v , v 1 , v 2 , … , v p 1 − 1 } U_1=\{v,v_1,v_2,\ldots,v_{p_1-1}\} U 1 = { v , v 1 , v 2 , … , v p 1 − 1 } G ′ = G − U 1 G'=G-U_1 G ′ = G − U 1 G [ U 1 ] = K p 1 G[U_1]=K_{p_1} G [ U 1 ] = K p 1 G ′ = K c ∨ T n − p 1 − c , p 1 − 1 G'=K_c\vee T_{n-p_1-c,p_1-1} G ′ = K c ∨ T n − p 1 − c , p 1 − 1 n − p 1 ≥ p 2 + ⋯ + p ℓ n-p_1\ge p_2+\cdots+p_\ell n − p 1 ≥ p 2 + ⋯ + p ℓ G ′ G' G ′ K p 2 ∪ ⋯ ∪ K p ℓ K_{p_2}\cup\cdots\cup K_{p_\ell} K p 2 ∪ ⋯ ∪ K p ℓ G G G K p 1 ∪ ⋯ ∪ K p ℓ K_{p_1}\cup\cdots\cup K_{p_\ell} K p 1 ∪ ⋯ ∪ K p ℓ
Hence there is an index j 0 ∈ { 1 , … , p 1 − 1 } j_0\in\{1,\ldots,p_1-1\} j 0 ∈ { 1 , … , p 1 − 1 } N ( v ) ∩ V j 0 = ∅ N(v)\cap V_{j_0}=\varnothing N ( v ) ∩ V j 0 = ∅
n − 1 − ⌊ n − c − 1 p 1 − 1 ⌋ = d ( v ) ≤ n − 1 − ∣ V j 0 ∣ ≤ n − 1 − ⌈ n − c − 1 p 1 − 1 ⌉ , n-1-\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor=d(v)\le n-1-|V_{j_0}|\le n-1-\left\lceil\frac{n-c-1}{p_1-1}\right\rceil, n − 1 − ⌊ p 1 − 1 n − c − 1 ⌋ = d ( v ) ≤ n − 1 − ∣ V j 0 ∣ ≤ n − 1 − ⌈ p 1 − 1 n − c − 1 ⌉ , N ( v ) = V ( G ) ∖ ( V j 0 ∪ { v } ) N(v)=V(G)\setminus(V_{j_0}\cup\{v\}) N ( v ) = V ( G ) ∖ ( V j 0 ∪ { v }) ∣ V j 0 ∣ = ⌊ n − c − 1 p 1 − 1 ⌋ |V_{j_0}|=\left\lfloor\frac{n-c-1}{p_1-1}\right\rfloor ∣ V j 0 ∣ = ⌊ p 1 − 1 n − c − 1 ⌋ G = K c ∨ T n − c , p 1 − 1 G=K_c\vee T_{n-c,p_1-1} G = K c ∨ T n − c , p 1 − 1
Proof of Theorem 4. Let G ∈ EX ( p + q + r , K ‾ p ∪ K ‾ q ∪ K ‾ r ) G \in\operatorname{EX}(p+q+r, \overline{K}_p \cup\overline{K}_q \cup\overline{K}_r) G ∈ EX ( p + q + r , K p ∪ K q ∪ K r ) t ≥ 1 t \ge1 t ≥ 1 t t t K ‾ 4 ∪ K ‾ p + q + r − 4 \overline{K}_4 \cup\overline{K}_{p+q+r-4} K 4 ∪ K p + q + r − 4 t − 1 t-1 t − 1 K ‾ p + q + r − 4 \overline{K}_{p+q+r-4} K p + q + r − 4 ( p − 1 ) + ( q − 1 ) + ( r − 1 ) − ( p + q + r − 4 ) = 1 (p-1)+(q-1)+(r-1)-(p+q+r-4)=1 ( p − 1 ) + ( q − 1 ) + ( r − 1 ) − ( p + q + r − 4 ) = 1 K ‾ 4 ∪ K ‾ p + q + r − 4 \overline{K}_4 \cup\overline{K}_{p+q+r-4} K 4 ∪ K p + q + r − 4 p p p q q q r r r T ‾ n , p − 1 \overline{T}_{n,p-1} T n , p − 1 K ‾ p \overline{K}_p K p e ( G ) ≤ min { 6 , t n , p − 1 } e(G) \le\min\{6,t_{n,p-1}\} e ( G ) ≤ min { 6 , t n , p − 1 }
Claim 8.2. If G G G K ‾ p \overline{K}_p K p e ( G ) ≤ 6 e(G) \le6 e ( G ) ≤ 6
G = K ‾ 4 ∪ K ‾ n − 4 G=\overline{K}_4 \cup\overline{K}_{n-4} G = K 4 ∪ K n − 4
( p , q , r ) = ( 3 , 2 , 2 ) (p,q,r)=(3,2,2) ( p , q , r ) = ( 3 , 2 , 2 ) G = K 1 , 6 G=K_{1,6} G = K 1 , 6
Proof. By e ( G ) ≤ 6 < 9 ≤ 3 ( s + r ) e(G) \le6 < 9 \le3(s+r) e ( G ) ≤ 6 < 9 ≤ 3 ( s + r ) Theorem 7 , G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q e ( G ) ≤ 5 e(G) \le5 e ( G ) ≤ 5 G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r e ( G ) = 6 e(G)=6 e ( G ) = 6
If Δ ( G ) = 6 \Delta(G)=6 Δ ( G ) = 6 G = K 1 , 6 ∪ K ‾ p + q + r − 7 G=K_{1,6}\cup\overline{K}_{p+q+r-7} G = K 1 , 6 ∪ K p + q + r − 7 p + q + r − 7 ≠ 0 p+q+r-7 \ne0 p + q + r − 7 = 0 K 1 , 6 ∪ K ‾ p + q + r − 7 K_{1,6}\cup\overline{K}_{p+q+r-7} K 1 , 6 ∪ K p + q + r − 7 K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r p + q + r − 7 = 0 p+q+r-7=0 p + q + r − 7 = 0 p ≥ q ≥ r ≥ 2 p \ge q \ge r \ge2 p ≥ q ≥ r ≥ 2 ( p , q , r ) = ( 3 , 2 , 2 ) (p,q,r)=(3,2,2) ( p , q , r ) = ( 3 , 2 , 2 )
If Δ ( G ) ≤ 5 \Delta(G)\le5 Δ ( G ) ≤ 5 P , Q ⊆ V ( G ) P,Q \subseteq V(G) P , Q ⊆ V ( G ) G [ P ] = K ‾ p G[P]=\overline{K}_p G [ P ] = K p G [ Q ] = K ‾ q G[Q]=\overline{K}_q G [ Q ] = K q P P P Q Q Q
(M1) G − P − Q G-P-Q G − P − Q
(M2) modulo (M1), e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ]
If ∣ E ( P , V ( G ) ∖ P ) ∣ ≥ 4 |E(P,V(G)\setminus P)|\ge4 ∣ E ( P , V ( G ) ∖ P ) ∣ ≥ 4 ∣ E ( Q , V ( G ) ∖ Q ) ∣ ≥ 4 |E(Q,V(G)\setminus Q)|\ge4 ∣ E ( Q , V ( G ) ∖ Q ) ∣ ≥ 4 e ( G − P ) ≤ 2 e(G-P)\le2 e ( G − P ) ≤ 2 e ( G − Q ) ≤ 2 e(G-Q)\le2 e ( G − Q ) ≤ 2 Theorem 7 , in these cases G − P G-P G − P K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r G − Q G-Q G − Q K ‾ p \overline{K}_p K p K ‾ r \overline{K}_r K r
Suppose ∣ E ( P , V ( G ) ∖ P ) ∣ ≤ 3 |E(P,V(G)\setminus P)|\le3 ∣ E ( P , V ( G ) ∖ P ) ∣ ≤ 3 ∣ E ( Q , V ( G ) ∖ Q ) ∣ ≤ 3 |E(Q,V(G)\setminus Q)|\le3 ∣ E ( Q , V ( G ) ∖ Q ) ∣ ≤ 3 G − P − Q G-P-Q G − P − Q G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r R = V ( G ) − P − Q R=V(G)-P-Q R = V ( G ) − P − Q x y ∈ E ( G ) xy\in E(G) x y ∈ E ( G ) x , y ∈ R x,y\in R x , y ∈ R (11) , we have the following properties.
(A) If x (or y ) has no neighbors in some J ∈ { P , Q } , then each w ∈ J has a neighbor in R ; and (B) If x (or y ) has exactly one neighbor w in some J ∈ { P , Q } , then w has another neighbor in R ; and (C) For each J ∈ { P , Q } , e [ J , R ] ≥ 2 with equality only if ∣ J ∣ = 2 or some w ∈ J is adjacent to both x and y . (28) \begin{aligned}
\text{(A)}\quad&\text{If }x\text{ (or }y\text{) has no neighbors in some }J\in\{P,Q\},\text{ then each }w\in J\text{ has a neighbor in }R;\text{ and}\\
\text{(B)}\quad&\text{If }x\text{ (or }y\text{) has exactly one neighbor }w\text{ in some }J\in\{P,Q\},\text{ then }w\text{ has another neighbor in }R;\text{ and}\\
\text{(C)}\quad&\text{For each }J\in\{P,Q\},\ e[J,R]\ge2\text{ with equality only if }|J|=2\text{ or some }w\in J\\
&\text{is adjacent to both }x\text{ and }y. \tag*{(28)}
\end{aligned} (A) (B) (C) If x (or y ) has no neighbors in some J ∈ { P , Q } , then each w ∈ J has a neighbor in R ; and If x (or y ) has exactly one neighbor w in some J ∈ { P , Q } , then w has another neighbor in R ; and For each J ∈ { P , Q } , e [ J , R ] ≥ 2 with equality only if ∣ J ∣ = 2 or some w ∈ J is adjacent to both x and y . (28) Recall that e ( G ) = 6 e(G)=6 e ( G ) = 6 p ≥ q ≥ r ≥ 2 p\ge q\ge r\ge2 p ≥ q ≥ r ≥ 2 ( p , q , r ) ≠ ( 2 , 2 , 2 ) (p,q,r)\ne(2,2,2) ( p , q , r ) = ( 2 , 2 , 2 ) p ≥ 3 p\ge3 p ≥ 3 e ( G [ R ] ) ≤ 2 e(G[R])\le2 e ( G [ R ]) ≤ 2 e ( G [ R ] ) = 2 e(G[R])=2 e ( G [ R ]) = 2 e [ P , R ] = 2 e[P,R]=2 e [ P , R ] = 2 e [ Q , R ] = 2 e[Q,R]=2 e [ Q , R ] = 2 w r ∈ R − { x , y } w_r\in R-\{x,y\} w r ∈ R − { x , y } G [ R ] G[R] G [ R ] P P P w r w_r w r P P P P P P R R R e ( G [ R ] ) = 1 e(G[R])=1 e ( G [ R ]) = 1
If e [ P , Q ] = 0 e[P,Q]=0 e [ P , Q ] = 0 J ∈ { P , Q } J\in\{P,Q\} J ∈ { P , Q } e [ J , R ] = 3 e[J,R]=3 e [ J , R ] = 3 e [ P , R ] = 3 e[P,R]=3 e [ P , R ] = 3 e [ Q , R ] = 2 e[Q,R]=2 e [ Q , R ] = 2 ∣ Q ∣ = 2 |Q|=2 ∣ Q ∣ = 2 Q = { w q 1 , w q 2 } Q=\{w_{q_1},w_{q_2}\} Q = { w q 1 , w q 2 } x w q 1 , x w q 2 ∈ E ( G ) xw_{q_1},xw_{q_2}\in E(G) x w q 1 , x w q 2 ∈ E ( G ) Δ ( G ) ≤ 5 \Delta(G)\le5 Δ ( G ) ≤ 5 w p ∈ P w_p\in P w p ∈ P N ( w p ) = ∅ N(w_p)=\varnothing N ( w p ) = ∅ w p w_p w p P P P y y y w p w_p w p Q Q Q w q 1 w_{q_1} w q 1 P P P e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ] P = { w p 1 , w p 2 , w p 3 } P=\{w_{p_1},w_{p_2},w_{p_3}\} P = { w p 1 , w p 2 , w p 3 } P ′ = { w p 1 , w p 2 , x } P'=\{w_{p_1},w_{p_2},x\} P ′ = { w p 1 , w p 2 , x } Q ′ = { w q 1 , w p 3 } Q'=\{w_{q_1},w_{p_3}\} Q ′ = { w q 1 , w p 3 } R ′ = { w q 2 , y } R'=\{w_{q_2},y\} R ′ = { w q 2 , y } w q ∈ Q w_q\in Q w q ∈ Q x w q , y w q ∈ E ( G ) xw_q,yw_q\in E(G) x w q , y w q ∈ E ( G ) e [ P , R ] = 3 e[P,R]=3 e [ P , R ] = 3 w p ′ ∈ P w'_p\in P w p ′ ∈ P d ( w p ′ ) ≤ 1 d(w'_p)\le1 d ( w p ′ ) ≤ 1 w p ′ w'_p w p ′ w q w_q w q e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ]
If e [ Q , R ] = 3 e[Q,R]=3 e [ Q , R ] = 3 e [ P , R ] = 2 e[P,R]=2 e [ P , R ] = 2 z q ∈ Q z_q\in Q z q ∈ Q ∣ N ( z q ) ∣ ≥ 1 |N(z_q)|\ge1 ∣ N ( z q ) ∣ ≥ 1 p ≥ 3 p\ge3 p ≥ 3 z p ∈ P z_p\in P z p ∈ P N ( z p ) = ∅ N(z_p)=\varnothing N ( z p ) = ∅ z p z_p z p z q z_q z q e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ]
If e [ P , Q ] = 1 e[P,Q]=1 e [ P , Q ] = 1 e [ J , R ] = 2 e[J,R]=2 e [ J , R ] = 2 J ∈ { P , Q } J\in\{P,Q\} J ∈ { P , Q } ∣ P ∣ ≥ 3 |P|\ge3 ∣ P ∣ ≥ 3 u P ∈ P u_P\in P u P ∈ P x x x y y y ∣ Q ∣ = 2 |Q|=2 ∣ Q ∣ = 2 Q = { u q 1 , u q 2 } Q=\{u_{q_1},u_{q_2}\} Q = { u q 1 , u q 2 } x u q 1 , x u q 2 ∈ E ( G ) xu_{q_1},xu_{q_2}\in E(G) x u q 1 , x u q 2 ∈ E ( G ) N ( u q 1 ) ∩ P = ∅ N(u_{q_1})\cap P=\varnothing N ( u q 1 ) ∩ P = ∅ u q 1 u_{q_1} u q 1 P P P P P P Q Q Q e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ]
Suppose that there is a vertex u Q ∈ Q u_Q\in Q u Q ∈ Q x x x y y y u P u Q ∉ E ( G ) u_Pu_Q\notin E(G) u P u Q ∈ / E ( G ) ∣ N ( u Q ) ∩ P ∣ = 0 |N(u_Q)\cap P|=0 ∣ N ( u Q ) ∩ P ∣ = 0 u Q u_Q u Q P P P P P P Q Q Q e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ] u P u Q ∉ E ( G ) u_Pu_Q\notin E(G) u P u Q ∈ / E ( G ) ∣ N ( u Q ) ∩ P ∣ = 1 |N(u_Q)\cap P|=1 ∣ N ( u Q ) ∩ P ∣ = 1 u Q u_Q u Q u Q u_Q u Q P P P e [ P , V ( G ) ∖ P ] e[P,V(G)\setminus P] e [ P , V ( G ) ∖ P ] u P u Q ∈ E ( G ) u_Pu_Q\in E(G) u P u Q ∈ E ( G ) G = K 4 ∪ K ‾ n − 4 G=K_4\cup\overline{K}_{n-4} G = K 4 ∪ K n − 4
If G G G K ‾ p \overline{K}_p K p G = T ‾ n , p − 1 G=\overline{T}_{n,p-1} G = T n , p − 1 G G G K ‾ p \overline{K}_p K p G = K 4 ∪ K ‾ n − 4 G=K_4\cup\overline{K}_{n-4} G = K 4 ∪ K n − 4 ( p , q , r ) = ( 3 , 2 , 2 ) (p,q,r)=(3,2,2) ( p , q , r ) = ( 3 , 2 , 2 ) G = K 1 , 6 G=K_{1,6} G = K 1 , 6 t ‾ n , p − 1 = 6 \overline{t}_{n,p-1}=6 t n , p − 1 = 6 ( p , q , r ) = ( 5 , 2 , 2 ) (p,q,r)=(5,2,2) ( p , q , r ) = ( 5 , 2 , 2 ) p ≥ 7 p\ge7 p ≥ 7 ( q , r ) = ( 3 , 2 ) (q,r)=(3,2) ( q , r ) = ( 3 , 2 ) t ‾ n , p − 1 = 5 \overline{t}_{n,p-1}=5 t n , p − 1 = 5 p ≥ 6 p\ge6 p ≥ 6 q = r = 2 q=r=2 q = r = 2 t ‾ n , p − 1 > 6 \overline{t}_{n,p-1}>6 t n , p − 1 > 6
Proof of Theorem 5
Recall that
c = c q + c r , c=c_q+c_r, c = c q + c r , where p ≥ q ≥ r p\ge q\ge r p ≥ q ≥ r c q = { 0 , if p > q , 1 , if p = q , c_q=\begin{cases}0,&\text{if }p>q,\\1,&\text{if }p=q,\end{cases} c q = { 0 , 1 , if p > q , if p = q , c r = { 0 , if p > r , 1 , if p = r . c_r=\begin{cases}0,&\text{if }p>r,\\1,&\text{if }p=r.\end{cases} c r = { 0 , 1 , if p > r , if p = r .
Lemma 9.1. For any z ≤ p − 1 z\le p-1 z ≤ p − 1 K 3 , 4 ( n , z ) ∪ { K 3 , 4 ∗ ( n ) } \mathcal{K}_{3,4}(n,z)\cup\{K^*_{3,4}(n)\} K 3 , 4 ( n , z ) ∪ { K 3 , 4 ∗ ( n )} K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q
Proof. Let z ≤ p − 1 z\le p-1 z ≤ p − 1 G ∈ K 3 , 4 ( n , z ) G\in\mathcal{K}_{3,4}(n,z) G ∈ K 3 , 4 ( n , z ) G = K 3 , 4 ( n , x , y ) G=\mathcal{K}_{3,4}(n,x,y) G = K 3 , 4 ( n , x , y ) x + 2 y = n − p − q + 1 x+2y=n-p-q+1 x + 2 y = n − p − q + 1 3 x + 4 y ≤ n 3x+4y\le n 3 x + 4 y ≤ n x + y ≤ z x+y\le z x + y ≤ z t ∈ { p , q } t\in\{p,q\} t ∈ { p , q } G G G t − x − y t-x-y t − x − y ( n − 3 x − 4 y ) K 1 (n-3x-4y)K_1 ( n − 3 x − 4 y ) K 1 ( p − x − y ) + ( q − x − y ) − ( n − 3 x − 4 y ) = p + q + x + 2 y − n = 1 (p-x-y)+(q-x-y)-(n-3x-4y)=p+q+x+2y-n=1 ( p − x − y ) + ( q − x − y ) − ( n − 3 x − 4 y ) = p + q + x + 2 y − n = 1 p p p q q q
Suppose G = K 3 , 4 ∗ ( n ) = ( 2 p + 2 q − 4 − n ) K 3 ∪ ( n − 3 ( p + q ) 2 + 2 ) K 4 ∪ K 1 , 3 G=K^*_{3,4}(n)=(2p+2q-4-n)K_3\cup\left(n-\frac{3(p+q)}{2}+2\right)K_4\cup K_{1,3} G = K 3 , 4 ∗ ( n ) = ( 2 p + 2 q − 4 − n ) K 3 ∪ ( n − 2 3 ( p + q ) + 2 ) K 4 ∪ K 1 , 3 p = q p=q p = q K 1 , 3 K_{1,3} K 1 , 3 K ‾ 2 \overline{K}_2 K 2 G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q
Lemma 9.2. For any z ≤ p − 1 z\le p-1 z ≤ p − 1 K 5 , 6 ( n , z ) ∪ { K 5 , 6 ∗ ( n ) } \mathcal{K}_{5,6}(n,z)\cup\{K^*_{5,6}(n)\} K 5 , 6 ( n , z ) ∪ { K 5 , 6 ∗ ( n )} K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r
Proof. Let z ≤ p − 1 z\le p-1 z ≤ p − 1 G ∈ K 5 , 6 ( n , z ) G\in\mathcal{K}_{5,6}(n,z) G ∈ K 5 , 6 ( n , z ) G = K 5 , 6 ( n , x , y ) G=\mathcal{K}_{5,6}(n,x,y) G = K 5 , 6 ( n , x , y ) 2 x + 3 y = n − p − q − r + 1 2x+3y=n-p-q-r+1 2 x + 3 y = n − p − q − r + 1 5 x + 6 y ≤ n 5x+6y\le n 5 x + 6 y ≤ n x + y ≤ z x+y\le z x + y ≤ z t ∈ { p , q , r } t\in\{p,q,r\} t ∈ { p , q , r } G G G t − x − y t-x-y t − x − y ( n − 5 x − 6 y ) K 1 (n-5x-6y)K_1 ( n − 5 x − 6 y ) K 1 ( p − x − y ) + ( q − x − y ) + ( r − x − y ) − ( n − 5 x − 6 y ) = p + q + r + 2 x + 3 y − n = 1 (p-x-y)+(q-x-y)+(r-x-y)-(n-5x-6y)=p+q+r+2x+3y-n=1 ( p − x − y ) + ( q − x − y ) + ( r − x − y ) − ( n − 5 x − 6 y ) = p + q + r + 2 x + 3 y − n = 1 G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r
Suppose now G = K 5 , 6 ∗ ( n ) = ( 2 p + 2 q + 2 r − 6 − n ) K 5 ∪ ( n − 5 ( p + q + r ) 3 + 4 ) K 6 ∪ K 1 , 5 G=K^*_{5,6}(n)=(2p+2q+2r-6-n)K_5\cup\left(n-\frac{5(p+q+r)}{3}+4\right)K_6\cup K_{1,5} G = K 5 , 6 ∗ ( n ) = ( 2 p + 2 q + 2 r − 6 − n ) K 5 ∪ ( n − 3 5 ( p + q + r ) + 4 ) K 6 ∪ K 1 , 5 p = q = r p=q=r p = q = r K 1 , 5 K_{1,5} K 1 , 5 K ‾ 2 \overline{K}_2 K 2 G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r
Lemma 9.3. If n ∈ [ p + q , 3 ( p − 1 ) + c q ] n \in[p+q,3(p-1)+c_q] n ∈ [ p + q , 3 ( p − 1 ) + c q ]
3 ( n − p − q + 1 ) ≤ t ˉ n − c q , p − 1 , (29) 3(n-p-q+1) \le\bar{t}_{n-c_q,p-1}, \tag*{(29)} 3 ( n − p − q + 1 ) ≤ t ˉ n − c q , p − 1 , (29) then there is a graph G ∈ K 3 , 4 ( n , p − 1 ) G \in\mathcal{K}_{3,4}(n,p-1) G ∈ K 3 , 4 ( n , p − 1 ) e ( G ) ≤ 3 ( n − p − q + 1 ) e(G) \le3(n-p-q+1) e ( G ) ≤ 3 ( n − p − q + 1 ) n ∈ [ 3 ( p − 1 ) + c q , 4 ( p − 1 ) + c q ] n \in[3(p-1)+c_q,4(p-1)+c_q] n ∈ [ 3 ( p − 1 ) + c q , 4 ( p − 1 ) + c q ] 3 ( n − p − q + 1 ) ≥ t ˉ n − c q , p − 1 3(n-p-q+1) \ge\bar{t}_{n-c_q,p-1} 3 ( n − p − q + 1 ) ≥ t ˉ n − c q , p − 1
Proof. First suppose that p + q ≤ n ≤ 3 ( p − 1 ) + c q p+q \le n \le3(p-1)+c_q p + q ≤ n ≤ 3 ( p − 1 ) + c q T ‾ n − c q , p − 1 \overline{T}_{n-c_q,p-1} T n − c q , p − 1 t ˉ n − c q , p − 1 ≤ 2 ( n − c q ) 2 = n − c q \bar{t}_{n-c_q,p-1} \le\frac{2(n-c_q)}{2}=n-c_q t ˉ n − c q , p − 1 ≤ 2 2 ( n − c q ) = n − c q t ˉ n − c q , p − 1 ≤ 3 ( p − 1 ) \bar{t}_{n-c_q,p-1} \le3(p-1) t ˉ n − c q , p − 1 ≤ 3 ( p − 1 ) 3 ( n − p − q + 1 ) ≤ n − c q 3(n-p-q+1) \le n-c_q 3 ( n − p − q + 1 ) ≤ n − c q n − p − q + 1 ≤ p − 1 n-p-q+1 \le p-1 n − p − q + 1 ≤ p − 1 k = ⌈ ( n − p − q + 1 ) / 2 ⌉ k=\lceil(n-p-q+1)/2\rceil k = ⌈( n − p − q + 1 ) /2 ⌉ x = 2 k − ( n − p − q + 1 ) x=2k-(n-p-q+1) x = 2 k − ( n − p − q + 1 ) y = n − p − q + 1 − k y=n-p-q+1-k y = n − p − q + 1 − k n − p − q + 1 ≥ 1 n-p-q+1 \ge1 n − p − q + 1 ≥ 1 x ∈ { 0 , 1 } x \in\{0,1\} x ∈ { 0 , 1 } y ≥ 0 y \ge0 y ≥ 0
x + 2 y = n − p − q + 1 , x + y = k ≤ n − p − q + 1 ≤ p − 1 , x+2y=n-p-q+1,\qquad x+y=k\le n-p-q+1\le p-1, x + 2 y = n − p − q + 1 , x + y = k ≤ n − p − q + 1 ≤ p − 1 , and
3 x + 4 y = n − p − q + 1 + 2 k ≤ 3 ( n − p − q + 1 ) ≤ n − c q ≤ n . 3x+4y=n-p-q+1+2k\le3(n-p-q+1)\le n-c_q\le n. 3 x + 4 y = n − p − q + 1 + 2 k ≤ 3 ( n − p − q + 1 ) ≤ n − c q ≤ n . Thus K 3 , 4 ( n , x , y ) ∈ K 3 , 4 ( n , p − 1 ) \mathcal{K}_{3,4}(n,x,y) \in\mathcal{K}_{3,4}(n,p-1) K 3 , 4 ( n , x , y ) ∈ K 3 , 4 ( n , p − 1 ) e ( K 3 , 4 ( n , x , y ) ) = 3 ( n − p − q + 1 ) e(\mathcal{K}_{3,4}(n,x,y))=3(n-p-q+1) e ( K 3 , 4 ( n , x , y )) = 3 ( n − p − q + 1 )
Suppose that 3 ( p − 1 ) + c q ≤ n ≤ 4 ( p − 1 ) + c q 3(p-1)+c_q \le n \le4(p-1)+c_q 3 ( p − 1 ) + c q ≤ n ≤ 4 ( p − 1 ) + c q t ˉ n − c q , p − 1 = 3 ( n − c q ) − 6 ( p − 1 ) \bar{t}_{n-c_q,p-1}=3(n-c_q)-6(p-1) t ˉ n − c q , p − 1 = 3 ( n − c q ) − 6 ( p − 1 ) c q c_q c q q ≤ p − 1 + c q q \le p-1+c_q q ≤ p − 1 + c q
3 ( n − p − q + 1 ) ≥ 3 ( n − 2 ( p − 1 ) − c q ) = t ˉ n − c q , p − 1 . 3(n-p-q+1)\ge3(n-2(p-1)-c_q)=\bar{t}_{n-c_q,p-1}. 3 ( n − p − q + 1 ) ≥ 3 ( n − 2 ( p − 1 ) − c q ) = t ˉ n − c q , p − 1 . Lemma 9.4. If n ∈ [ p + q + r + 1 , 5 ( p − 1 ) + c ] n \in[p+q+r+1,5(p-1)+c] n ∈ [ p + q + r + 1 , 5 ( p − 1 ) + c ]
5 s ≤ t ˉ n − c , p − 1 , (30) 5s\le\bar{t}_{n-c,p-1}, \tag*{(30)} 5 s ≤ t ˉ n − c , p − 1 , (30) then there is a graph G ∈ K 5 , 6 ( n , p − 1 ) G \in\mathcal{K}_{5,6}(n,p-1) G ∈ K 5 , 6 ( n , p − 1 ) e ( G ) ≤ 5 s e(G)\le5s e ( G ) ≤ 5 s n ∈ [ 5 ( p − 1 ) + c , 6 ( p − 1 ) + c ] n \in[5(p-1)+c,6(p-1)+c] n ∈ [ 5 ( p − 1 ) + c , 6 ( p − 1 ) + c ] 5 s ≥ t ˉ n − c , p − 1 5s\ge\bar{t}_{n-c,p-1} 5 s ≥ t ˉ n − c , p − 1
Proof. First suppose that p + q + r + 1 ≤ n ≤ 5 ( p − 1 ) + c p+q+r+1\le n\le5(p-1)+c p + q + r + 1 ≤ n ≤ 5 ( p − 1 ) + c T ‾ n − c , p − 1 \overline{T}_{n-c,p-1} T n − c , p − 1 t ˉ n − c , p − 1 ≤ 4 ( n − c ) 2 = 2 ( n − c ) \bar{t}_{n-c,p-1}\le\frac{4(n-c)}{2}=2(n-c) t ˉ n − c , p − 1 ≤ 2 4 ( n − c ) = 2 ( n − c ) t ˉ n − c , p − 1 ≤ 10 ( p − 1 ) \bar{t}_{n-c,p-1}\le10(p-1) t ˉ n − c , p − 1 ≤ 10 ( p − 1 ) 5 s ≤ 2 ( n − c ) 5s\le2(n-c) 5 s ≤ 2 ( n − c ) s ≤ 2 ( p − 1 ) s\le2(p-1) s ≤ 2 ( p − 1 ) k = ⌈ s / 3 ⌉ k=\lceil s/3\rceil k = ⌈ s /3 ⌉ x = 3 k − s x=3k-s x = 3 k − s y = s − 2 k y=s-2k y = s − 2 k s ≥ 2 s\ge2 s ≥ 2 k ≤ s / 2 k\le s/2 k ≤ s /2 x , y x,y x , y
2 x + 3 y = s , x + y = k ≤ p − 1 , 5 x + 6 y = s + 3 k ≤ 5 s 2 ≤ n − c ≤ n . 2x+3y=s,\qquad x+y=k\le p-1,\qquad5x+6y=s+3k\le\frac{5s}{2}\le n-c\le n. 2 x + 3 y = s , x + y = k ≤ p − 1 , 5 x + 6 y = s + 3 k ≤ 2 5 s ≤ n − c ≤ n . Thus K 5 , 6 ( n , x , y ) ∈ K 5 , 6 ( n , p − 1 ) \mathcal{K}_{5,6}(n,x,y)\in\mathcal{K}_{5,6}(n,p-1) K 5 , 6 ( n , x , y ) ∈ K 5 , 6 ( n , p − 1 ) e ( K 5 , 6 ( n , x , y ) ) = 5 s e(\mathcal{K}_{5,6}(n,x,y))=5s e ( K 5 , 6 ( n , x , y )) = 5 s
Suppose that 5 ( p − 1 ) + c ≤ n ≤ 6 ( p − 1 ) + c 5(p-1)+c\le n\le6(p-1)+c 5 ( p − 1 ) + c ≤ n ≤ 6 ( p − 1 ) + c t ˉ n − c , p − 1 = 5 ( n − c ) − 15 ( p − 1 ) \bar{t}_{n-c,p-1}=5(n-c)-15(p-1) t ˉ n − c , p − 1 = 5 ( n − c ) − 15 ( p − 1 ) c c c
5 s = 5 ( n − p − q − r + 1 ) ≥ 5 ( n − 3 ( p − 1 ) − c ) = t ˉ n − c , p − 1 . 5s=5(n-p-q-r+1)\ge5(n-3(p-1)-c)=\bar{t}_{n-c,p-1}. 5 s = 5 ( n − p − q − r + 1 ) ≥ 5 ( n − 3 ( p − 1 ) − c ) = t ˉ n − c , p − 1 . Proof of Theorem 5. Let G G G n n n p p p q q q r r r e ( G ) = ex ( n , K p ∪ K q ∪ K r ) e(G)=\operatorname{ex}(n,K_p\cup K_q\cup K_r) e ( G ) = ex ( n , K p ∪ K q ∪ K r ) G G G
e ( G ) ≤ t ˉ n − c , p − 1 . (31) e(G)\le\bar{t}_{n-c,p-1}. \tag*{(31)} e ( G ) ≤ t ˉ n − c , p − 1 . (31) If G G G K ‾ p \overline{K}_p K p e ( G ) ≥ t ‾ n , p − 1 ≥ t ‾ n − c , p − 1 e(G) \ge\overline{t}_{n,p-1} \ge\overline{t}_{n-c,p-1} e ( G ) ≥ t n , p − 1 ≥ t n − c , p − 1 c = 0 c=0 c = 0 e ( G ) = t ‾ n − c , p − 1 e(G)=\overline{t}_{n-c,p-1} e ( G ) = t n − c , p − 1 G G G K ‾ p \overline{K}_p K p
Case 1: G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q e ∈ E ( G ) e \in E(G) e ∈ E ( G ) G − e G-e G − e K ‾ p \overline{K}_p K p G G G c ≤ 1 c \le1 c ≤ 1 ex ‾ ( n , K p ∪ K q ∪ K r ) ≤ ex ‾ ( n , K p ∪ K q ) \overline{\operatorname{ex}}(n,K_p \cup K_q \cup K_r) \le\overline{\operatorname{ex}}(n,K_p \cup K_q) ex ( n , K p ∪ K q ∪ K r ) ≤ ex ( n , K p ∪ K q ) e ( G ) = ex ‾ ( n , K p ∪ K q ) e(G)=\overline{\operatorname{ex}}(n,K_p \cup K_q) e ( G ) = ex ( n , K p ∪ K q )
By Theorem 7 and (9.3), 3 ( r + s ) ≤ e ( G ) ≤ t ‾ n − c , p − 1 3(r+s) \le e(G) \le\overline{t}_{n-c,p-1} 3 ( r + s ) ≤ e ( G ) ≤ t n − c , p − 1 n ∈ [ p + q + r + 1 , 4 ( p − 1 ) + c ] n \in[p+q+r+1,4(p-1)+c] n ∈ [ p + q + r + 1 , 4 ( p − 1 ) + c ] e ( G ) = 3 ( r + s ) e(G)=3(r+s) e ( G ) = 3 ( r + s )
Assume that n ≥ 4 ( p − 1 ) + c + 1 n \ge4(p-1)+c+1 n ≥ 4 ( p − 1 ) + c + 1 t ‾ 4 ( p − 1 ) , p − 1 = 6 ( p − 1 ) \overline{t}_{4(p-1),p-1}=6(p-1) t 4 ( p − 1 ) , p − 1 = 6 ( p − 1 )
3 ( ( 4 ( p − 1 ) + c ) − p − q + 1 ) = 3 ( 3 p − 4 − ( q − c ) + 1 ) ≥ 3 ( 2 p − 2 ) = t ‾ 4 ( p − 1 ) , p − 1 , 3\left((4(p-1)+c)-p-q+1\right)=3(3p-4-(q-c)+1)\ge3(2p-2)=\overline{t}_{4(p-1),p-1}, 3 ( ( 4 ( p − 1 ) + c ) − p − q + 1 ) = 3 ( 3 p − 4 − ( q − c ) + 1 ) ≥ 3 ( 2 p − 2 ) = t 4 ( p − 1 ) , p − 1 , Theorem 10(1) for ℓ = 2 \ell=2 ℓ = 2 e ( G ) = ex ‾ ( n , K p ∪ K q ) = t ‾ n − c , p − 1 e(G)=\overline{\operatorname{ex}}(n,K_p \cup K_q)=\overline{t}_{n-c,p-1} e ( G ) = ex ( n , K p ∪ K q ) = t n − c , p − 1
Case 2: G G G K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q 5 s ≤ e ( G ) ≤ t ‾ n − c , p − 1 5s \le e(G) \le\overline{t}_{n-c,p-1} 5 s ≤ e ( G ) ≤ t n − c , p − 1 n ∈ [ p + q + r + 1 , 5 ( p − 1 ) + c ] n \in[p+q+r+1,5(p-1)+c] n ∈ [ p + q + r + 1 , 5 ( p − 1 ) + c ] e ( G ) = 5 s e(G)=5s e ( G ) = 5 s
Assume that n ≥ 5 ( p − 1 ) + c + 1 n \ge5(p-1)+c+1 n ≥ 5 ( p − 1 ) + c + 1 t ‾ 5 ( p − 1 ) , p − 1 = 10 ( p − 1 ) \overline{t}_{5(p-1),p-1}=10(p-1) t 5 ( p − 1 ) , p − 1 = 10 ( p − 1 )
5 ( ( 5 ( p − 1 ) + c ) − p − q − r + 1 ) ≥ { 5 ( 4 p − 5 − ( q − c ) − r + 1 ) ≥ 5 ( 2 p − 2 ) if c ≤ 1 , 5 ( 4 p − 5 − ( q − 1 ) − ( r − 1 ) + 1 ) ≥ 5 ( 2 p − 2 ) if c = 2 , 5\left((5(p-1)+c)-p-q-r+1\right)\ge
\begin{cases}
5(4p-5-(q-c)-r+1)\ge5(2p-2) & \text{if } c\le1,\\
5(4p-5-(q-1)-(r-1)+1)\ge5(2p-2) & \text{if } c=2,
\end{cases} 5 ( ( 5 ( p − 1 ) + c ) − p − q − r + 1 ) ≥ { 5 ( 4 p − 5 − ( q − c ) − r + 1 ) ≥ 5 ( 2 p − 2 ) 5 ( 4 p − 5 − ( q − 1 ) − ( r − 1 ) + 1 ) ≥ 5 ( 2 p − 2 ) if c ≤ 1 , if c = 2 , Theorem 10(1) for ℓ = 3 \ell=3 ℓ = 3 e ( G ) = ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n − c , p − 1 e(G)=\overline{\operatorname{ex}}(n,K_p \cup K_q \cup K_r)=\overline{t}_{n-c,p-1} e ( G ) = ex ( n , K p ∪ K q ∪ K r ) = t n − c , p − 1
Proof of Theorem 6
Let G n = EX ‾ ( n , K p ∪ K q ∪ K r ) \mathcal{G}_n=\overline{\operatorname{EX}}(n,K_p \cup K_q \cup K_r) G n = EX ( n , K p ∪ K q ∪ K r ) G ∈ G n G \in\mathcal{G}_n G ∈ G n e ( G ) ≤ t ‾ n − c , p − 1 e(G)\le\overline{t}_{n-c,p-1} e ( G ) ≤ t n − c , p − 1
Claim 10.1. Let G ∈ G n G \in\mathcal{G}_n G ∈ G n G G G K ‾ p \overline{K}_p K p c = 0 c=0 c = 0 G G G K ‾ p \overline{K}_p K p K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q c ≤ 1 c\le1 c ≤ 1
Proof. Let e ∈ E ( G ) e \in E(G) e ∈ E ( G ) G G G K ‾ p \overline{K}_p K p G − e G-e G − e K ‾ p \overline{K}_p K p c = 0 c=0 c = 0 G G G K ‾ p \overline{K}_p K p K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q G − e G-e G − e K ‾ p \overline{K}_p K p c ≤ 1 c\le1 c ≤ 1
Claim 10.2. (i) If n ≥ 4 ( p − 1 ) + c q n\ge4(p-1)+c_q n ≥ 4 ( p − 1 ) + c q EX ‾ ( n , K p ∪ K q ) = { K c q ∪ T ‾ n − c q , p − 1 } \overline{\operatorname{EX}}(n,K_p\cup K_q)=\{K_{c_q}\cup\overline{T}_{n-c_q,p-1}\} EX ( n , K p ∪ K q ) = { K c q ∪ T n − c q , p − 1 } n ≥ 6 ( p − 1 ) + c − 1 n\ge6(p-1)+c-1 n ≥ 6 ( p − 1 ) + c − 1 EX ‾ ( n , K p ∪ K q ∪ K r ) = { K c ∪ T ‾ n − c , p − 1 } \overline{\operatorname{EX}}(n,K_p\cup K_q\cup K_r)=\{K_c\cup\overline{T}_{n-c,p-1}\} EX ( n , K p ∪ K q ∪ K r ) = { K c ∪ T n − c , p − 1 }
Proof. Suppose there is J 4 ( p − 1 ) + c q ∈ EX ‾ ( 4 ( p − 1 ) + c q , K p ∪ K q ) J_{4(p-1)+c_q}\in\overline{\operatorname{EX}}(4(p-1)+c_q,K_p\cup K_q) J 4 ( p − 1 ) + c q ∈ EX ( 4 ( p − 1 ) + c q , K p ∪ K q ) e ( J 4 ( p − 1 ) + c q ) ≤ t ‾ 4 ( p − 1 ) , p − 1 e(J_{4(p-1)+c_q})\le\overline{t}_{4(p-1),p-1} e ( J 4 ( p − 1 ) + c q ) ≤ t 4 ( p − 1 ) , p − 1 J 4 ( p − 1 ) + c q J_{4(p-1)+c_q} J 4 ( p − 1 ) + c q K ‾ p \overline{K}_p K p c q = 0 c_q=0 c q = 0 J 4 ( p − 1 ) + c q = T ‾ 4 ( p − 1 ) , p − 1 J_{4(p-1)+c_q}=\overline{T}_{4(p-1),p-1} J 4 ( p − 1 ) + c q = T 4 ( p − 1 ) , p − 1
If J 4 ( p − 1 ) + c q J_{4(p-1)+c_q} J 4 ( p − 1 ) + c q K ‾ p \overline{K}_p K p e ( J 4 ( p − 1 ) + c q ) ≥ 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) e(J_{4(p-1)+c_q})\ge3(4(p-1)+c_q-p-q+1) e ( J 4 ( p − 1 ) + c q ) ≥ 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) t ‾ 4 ( p − 1 ) , p − 1 = 6 ( p − 1 ) \overline{t}_{4(p-1),p-1}=6(p-1) t 4 ( p − 1 ) , p − 1 = 6 ( p − 1 )
3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 3 ( 3 p − 3 + c q − q ) ≥ 3 ( 2 p − 2 ) = t ‾ 4 ( p − 1 ) , p − 1 , 3(4(p-1)+c_q-p-q+1)=3(3p-3+c_q-q)\ge3(2p-2)=\overline{t}_{4(p-1),p-1}, 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 3 ( 3 p − 3 + c q − q ) ≥ 3 ( 2 p − 2 ) = t 4 ( p − 1 ) , p − 1 , we have 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = t ‾ 4 ( p − 1 ) , p − 1 3(4(p-1)+c_q-p-q+1)=\overline{t}_{4(p-1),p-1} 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = t 4 ( p − 1 ) , p − 1
q = { p − 1 , if c q = 0 , p , if c q = 1. q=
\begin{cases}
p-1, & \text{if } c_q=0,\\
p, & \text{if } c_q=1.
\end{cases} q = { p − 1 , p , if c q = 0 , if c q = 1. By Theorem 7,
J 4 ( p − 1 ) + c q = x K 3 ∪ y K 4 ∪ K 4 ( p − 1 ) + c q − 3 x − 4 y or J 4 ( p − 1 ) + c q = x ′ K 3 ∪ y ′ K 4 ∪ K 1 , 3 . J_{4(p-1)+c_q}=xK_3\cup yK_4\cup K_{4(p-1)+c_q-3x-4y}
\quad\text{or}\quad
J_{4(p-1)+c_q}=x'K_3\cup y'K_4\cup K_{1,3}. J 4 ( p − 1 ) + c q = x K 3 ∪ y K 4 ∪ K 4 ( p − 1 ) + c q − 3 x − 4 y or J 4 ( p − 1 ) + c q = x ′ K 3 ∪ y ′ K 4 ∪ K 1 , 3 . holds, then since 3 x + 6 y = 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 6 ( p − 1 ) 3x+6y=3(4(p-1)+c_q-p-q+1)=6(p-1) 3 x + 6 y = 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 6 ( p − 1 ) 3 x + 4 y ≤ 4 ( p − 1 ) + c q 3x+4y\le4(p-1)+c_q 3 x + 4 y ≤ 4 ( p − 1 ) + c q x = 0 x=0 x = 0 y = p − 1 y=p-1 y = p − 1 c q = 0 c_q=0 c q = 0 J 4 ( p − 1 ) + c q = ( p − 1 ) K 4 J_{4(p-1)+c_q}=(p-1)K_4 J 4 ( p − 1 ) + c q = ( p − 1 ) K 4 ( p − 1 ) K 4 (p-1)K_4 ( p − 1 ) K 4 K ‾ p \overline{K}_p K p c q = 1 c_q=1 c q = 1 J 4 ( p − 1 ) + c q = K ‾ 1 ∪ ( p − 1 ) K 4 = K ‾ 1 ∪ T ‾ 4 ( p − 1 ) , p − 1 J_{4(p-1)+c_q}=\overline{K}_1\cup(p-1)K_4=\overline{K}_1\cup\overline{T}_{4(p-1),p-1} J 4 ( p − 1 ) + c q = K 1 ∪ ( p − 1 ) K 4 = K 1 ∪ T 4 ( p − 1 ) , p − 1 p = q p=q p = q 3 x ′ + 6 y ′ + 3 = 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 6 ( p − 1 ) 3x'+6y'+3=3(4(p-1)+c_q-p-q+1)=6(p-1) 3 x ′ + 6 y ′ + 3 = 3 ( 4 ( p − 1 ) + c q − p − q + 1 ) = 6 ( p − 1 ) 3 x ′ + 4 y ′ + 4 = 4 ( p − 1 ) + c q = 4 p − 3 3x'+4y'+4=4(p-1)+c_q=4p-3 3 x ′ + 4 y ′ + 4 = 4 ( p − 1 ) + c q = 4 p − 3 x ′ = − 1 x'=-1 x ′ = − 1 y ′ = p − 1 y'=p-1 y ′ = p − 1 EX ( 4 ( p − 1 ) + c q , K p ∪ K q ) = { K ‾ c q ∪ T ‾ 4 ( p − 1 ) , p − 1 } \operatorname{EX}(4(p-1)+c_q,K_p\cup K_q)=\{\overline{K}_{c_q}\cup\overline{T}_{4(p-1),p-1}\} EX ( 4 ( p − 1 ) + c q , K p ∪ K q ) = { K c q ∪ T 4 ( p − 1 ) , p − 1 } ℓ = 2 \ell=2 ℓ = 2 EX ( n , K p ∪ K q ) = { K ‾ c q ∪ T ‾ n − c q , p − 1 } \operatorname{EX}(n,K_p\cup K_q)=\{\overline{K}_{c_q}\cup\overline{T}_{n-c_q,p-1}\} EX ( n , K p ∪ K q ) = { K c q ∪ T n − c q , p − 1 } n ≥ 4 ( p − 1 ) + c q n\ge4(p-1)+c_q n ≥ 4 ( p − 1 ) + c q
Suppose that there is G 6 ( p − 1 ) + c − 1 ∈ EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ∪ K r ) G_{6(p-1)+c-1}\in\operatorname{EX}(6(p-1)+c-1,K_p\cup K_q\cup K_r) G 6 ( p − 1 ) + c − 1 ∈ EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ∪ K r ) e ( G 6 ( p − 1 ) + c − 1 ) ≤ t ‾ 6 ( p − 1 ) − 1 , p − 1 e(G_{6(p-1)+c-1})\le\overline{t}_{6(p-1)-1,p-1} e ( G 6 ( p − 1 ) + c − 1 ) ≤ t 6 ( p − 1 ) − 1 , p − 1 G 6 ( p − 1 ) + c − 1 G_{6(p-1)+c-1} G 6 ( p − 1 ) + c − 1 K ‾ p \overline{K}_p K p c = 0 c=0 c = 0 G 6 ( p − 1 ) + c − 1 = T ‾ 6 ( p − 1 ) − 1 , p − 1 G_{6(p-1)+c-1}=\overline{T}_{6(p-1)-1,p-1} G 6 ( p − 1 ) + c − 1 = T 6 ( p − 1 ) − 1 , p − 1
If G 6 ( p − 1 ) + c − 1 G_{6(p-1)+c-1} G 6 ( p − 1 ) + c − 1 K ‾ p \overline{K}_p K p K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q c ≤ 1 c\le1 c ≤ 1 e ( G 6 ( p − 1 ) + c − 1 ) ≥ ex ‾ ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) e(G_{6(p-1)+c-1})\ge\overline{\operatorname{ex}}(6(p-1)+c-1,K_p\cup K_q) e ( G 6 ( p − 1 ) + c − 1 ) ≥ ex ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) ex ‾ ( n , K p ∪ K q ∪ K r ) ≤ ex ‾ ( n , K p ∪ K q ) \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)\le\overline{\operatorname{ex}}(n,K_p\cup K_q) ex ( n , K p ∪ K q ∪ K r ) ≤ ex ( n , K p ∪ K q ) e ( G 6 ( p − 1 ) + c − 1 ) = ex ‾ ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) e(G_{6(p-1)+c-1})=\overline{\operatorname{ex}}(6(p-1)+c-1,K_p\cup K_q) e ( G 6 ( p − 1 ) + c − 1 ) = ex ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) G 6 ( p − 1 ) + c − 1 ∈ EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) G_{6(p-1)+c-1}\in\operatorname{EX}(6(p-1)+c-1,K_p\cup K_q) G 6 ( p − 1 ) + c − 1 ∈ EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ) G 6 ( p − 1 ) + c − 1 = K ‾ c ∪ T ‾ 6 ( p − 1 ) − 1 , p − 1 G_{6(p-1)+c-1}=\overline{K}_c\cup\overline{T}_{6(p-1)-1,p-1} G 6 ( p − 1 ) + c − 1 = K c ∪ T 6 ( p − 1 ) − 1 , p − 1
If G 6 ( p − 1 ) + c − 1 G_{6(p-1)+c-1} G 6 ( p − 1 ) + c − 1 K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q e ( G 6 ( p − 1 ) + c − 1 ) ≥ 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) e(G_{6(p-1)+c-1})\ge5(6(p-1)+c-1-p-q-r+1) e ( G 6 ( p − 1 ) + c − 1 ) ≥ 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) t ‾ 6 ( p − 1 ) − 1 , p − 1 = 15 ( p − 2 ) + 10 = 15 p − 20 \overline{t}_{6(p-1)-1,p-1}=15(p-2)+10=15p-20 t 6 ( p − 1 ) − 1 , p − 1 = 15 ( p − 2 ) + 10 = 15 p − 20
5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 5 ( 5 p − 6 + c − q − r ) ≥ 5 ( 3 p − 4 ) = t ‾ 6 ( p − 1 ) − 1 , p − 1 , 5(6(p-1)+c-1-p-q-r+1)=5(5p-6+c-q-r)\ge5(3p-4)=\overline{t}_{6(p-1)-1,p-1}, 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 5 ( 5 p − 6 + c − q − r ) ≥ 5 ( 3 p − 4 ) = t 6 ( p − 1 ) − 1 , p − 1 , we have 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = t ‾ 6 ( p − 1 ) − 1 , p − 1 5(6(p-1)+c-1-p-q-r+1)=\overline{t}_{6(p-1)-1,p-1} 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = t 6 ( p − 1 ) − 1 , p − 1
q = { p − 1 , if c = 0 , p , if c ≥ 1 , and r = { p − 1 , if c ≤ 1 , p , if c = 2. q=\begin{cases}
p-1, & \text{if }c=0,\\
p, & \text{if }c\ge1,
\end{cases}
\qquad\text{and}\qquad
r=\begin{cases}
p-1, & \text{if }c\le1,\\
p, & \text{if }c=2.
\end{cases} q = { p − 1 , p , if c = 0 , if c ≥ 1 , and r = { p − 1 , p , if c ≤ 1 , if c = 2. By Theorem 8, G 6 ( p − 1 ) + c − 1 = x K 5 ∪ y K 6 ∪ K ‾ 6 ( p − 1 ) + c − 1 − 5 x − 6 y G_{6(p-1)+c-1}=xK_5\cup yK_6\cup\overline{K}_{6(p-1)+c-1-5x-6y} G 6 ( p − 1 ) + c − 1 = x K 5 ∪ y K 6 ∪ K 6 ( p − 1 ) + c − 1 − 5 x − 6 y G 6 ( p − 1 ) + c − 1 = x ′ K 5 ∪ y ′ K 6 ∪ K 1 , 5 G_{6(p-1)+c-1}=x'K_5\cup y'K_6\cup K_{1,5} G 6 ( p − 1 ) + c − 1 = x ′ K 5 ∪ y ′ K 6 ∪ K 1 , 5
10 x + 15 y = 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 15 p − 20 10x+15y=5(6(p-1)+c-1-p-q-r+1)=15p-20 10 x + 15 y = 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 15 p − 20 and 5 x + 6 y ≤ 6 ( p − 1 ) + c − 1 5x+6y\le6(p-1)+c-1 5 x + 6 y ≤ 6 ( p − 1 ) + c − 1 x = 1 x=1 x = 1 y = p − 2 y=p-2 y = p − 2 c ≤ 1 c\le1 c ≤ 1 G 6 ( p − 1 ) + c − 1 = K ‾ c ∪ K 5 ∪ ( p − 2 ) K 6 G_{6(p-1)+c-1}=\overline{K}_c\cup K_5\cup(p-2)K_6 G 6 ( p − 1 ) + c − 1 = K c ∪ K 5 ∪ ( p − 2 ) K 6 K 5 ∪ ( p − 2 ) K 6 K_5\cup(p-2)K_6 K 5 ∪ ( p − 2 ) K 6 K ‾ 1 ∪ K 5 ∪ ( p − 2 ) K 6 \overline{K}_1\cup K_5\cup(p-2)K_6 K 1 ∪ K 5 ∪ ( p − 2 ) K 6 K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q c = 2 c=2 c = 2 G 6 ( p − 1 ) + c − 1 = K ‾ 2 ∪ K 5 ∪ ( p − 2 ) K 6 = K ‾ 2 ∪ T ‾ 6 ( p − 1 ) − 1 , p − 1 G_{6(p-1)+c-1}=\overline{K}_2\cup K_5\cup(p-2)K_6=\overline{K}_2\cup\overline{T}_{6(p-1)-1,p-1} G 6 ( p − 1 ) + c − 1 = K 2 ∪ K 5 ∪ ( p − 2 ) K 6 = K 2 ∪ T 6 ( p − 1 ) − 1 , p − 1 p = q = r p=q=r p = q = r
10 x ′ + 15 y ′ + 5 = 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 15 p − 20 10x'+15y'+5=5(6(p-1)+c-1-p-q-r+1)=15p-20 10 x ′ + 15 y ′ + 5 = 5 ( 6 ( p − 1 ) + c − 1 − p − q − r + 1 ) = 15 p − 20 and 5 x ′ + 6 y ′ + 6 = 6 ( p − 1 ) + c − 1 = 6 p − 5 5x'+6y'+6=6(p-1)+c-1=6p-5 5 x ′ + 6 y ′ + 6 = 6 ( p − 1 ) + c − 1 = 6 p − 5 x ′ = − 1 x'=-1 x ′ = − 1 y ′ = p − 1 y'=p-1 y ′ = p − 1 EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ∪ K r ) = { K ‾ c ∪ T ‾ 6 ( p − 1 ) − 1 , p − 1 } \operatorname{EX}(6(p-1)+c-1,K_p\cup K_q\cup K_r)=\{\overline{K}_c\cup\overline{T}_{6(p-1)-1,p-1}\} EX ( 6 ( p − 1 ) + c − 1 , K p ∪ K q ∪ K r ) = { K c ∪ T 6 ( p − 1 ) − 1 , p − 1 } ℓ = 3 \ell=3 ℓ = 3 EX ( n , K p ∪ K q ∪ K r ) = { K ‾ c ∪ T ‾ n − c , p − 1 } \operatorname{EX}(n,K_p\cup K_q\cup K_r)=\{\overline{K}_c\cup\overline{T}_{n-c,p-1}\} EX ( n , K p ∪ K q ∪ K r ) = { K c ∪ T n − c , p − 1 } n ≥ 6 ( p − 1 ) + c − 1 n\ge6(p-1)+c-1 n ≥ 6 ( p − 1 ) + c − 1
Claim 10.3
EX ( n , 2 K p ) = { K 3 , 4 ( n ) , if 2 p ≤ n ≤ 3 p − 3 , K 3 , 4 ( n ) ∪ { K 3 , 4 ∗ ( n ) } , if 3 p − 2 ≤ n ≤ 4 p − 4 , { K ‾ 1 ∪ T ‾ n − 1 , p − 1 } , n ≥ 4 p − 3. \operatorname{EX}(n,2K_p)= \begin{cases} K_{3,4}(n), & \text{if }2p\le n\le3p-3,\\ K_{3,4}(n)\cup\{K^*_{3,4}(n)\}, & \text{if }3p-2\le n\le4p-4,\\ \{\overline{K}_1\cup\overline{T}_{n-1,p-1}\}, & n\ge4p-3. \end{cases} EX ( n , 2 K p ) = ⎩ ⎨ ⎧ K 3 , 4 ( n ) , K 3 , 4 ( n ) ∪ { K 3 , 4 ∗ ( n )} , { K 1 ∪ T n − 1 , p − 1 } , if 2 p ≤ n ≤ 3 p − 3 , if 3 p − 2 ≤ n ≤ 4 p − 4 , n ≥ 4 p − 3.
Proof. Let J n ∈ EX ( n , 2 K p ) J_n\in\operatorname{EX}(n,2K_p) J n ∈ EX ( n , 2 K p ) e ( J n ) ≤ t ‾ n − 1 , p − 1 e(J_n)\le\overline{t}_{n-1,p-1} e ( J n ) ≤ t n − 1 , p − 1 J n J_n J n K ‾ p \overline{K}_p K p n ≥ 4 p − 3 n\ge4p-3 n ≥ 4 p − 3 EX ( n , 2 K p ) = { K ‾ 1 ∪ T ‾ n − 1 , p − 1 } \operatorname{EX}(n,2K_p)=\{\overline{K}_1\cup\overline{T}_{n-1,p-1}\} EX ( n , 2 K p ) = { K 1 ∪ T n − 1 , p − 1 }
Then we consider 2 p ≤ n ≤ 4 p − 4 2p\le n\le4p-4 2 p ≤ n ≤ 4 p − 4 J n ∈ K 3 , 4 ( n ) J_n\in K_{3,4}(n) J n ∈ K 3 , 4 ( n ) J n = x ′ K 3 ∪ y ′ K 4 ∪ K 1 , 3 J_n=x'K_3\cup y'K_4\cup K_{1,3} J n = x ′ K 3 ∪ y ′ K 4 ∪ K 1 , 3 3 x ′ + 6 y ′ + 3 = 3 ( n − 2 p + 1 ) 3x'+6y'+3=3(n-2p+1) 3 x ′ + 6 y ′ + 3 = 3 ( n − 2 p + 1 ) 3 x ′ + 4 y ′ + 4 = n 3x'+4y'+4=n 3 x ′ + 4 y ′ + 4 = n x ′ = 4 p − 4 − n x' = 4p - 4 - n x ′ = 4 p − 4 − n y ′ = n − 3 p + 2 y' = n - 3p + 2 y ′ = n − 3 p + 2 J n = K 3 , 4 ∗ ( n ) J_n = K^{*}_{3,4}(n) J n = K 3 , 4 ∗ ( n ) K ‾ 3 , 4 ( n ) ⊆ EX ‾ ( n , 2 K ‾ p ) \overline{K}_{3,4}(n) \subseteq\overline{\operatorname{EX}}(n, 2\overline{K}_p) K 3 , 4 ( n ) ⊆ EX ( n , 2 K p ) K 3 , 4 ∗ ( n ) ∈ EX ‾ ( n , 2 K ‾ p ) K^{*}_{3,4}(n) \in\overline{\operatorname{EX}}(n, 2\overline{K}_p) K 3 , 4 ∗ ( n ) ∈ EX ( n , 2 K p )
Claim 10.4. EX ‾ ( n , 3 K ‾ p ) = { K ‾ 5 , 6 ( n ) , if 3 p + 1 ≤ n ≤ 5 p − 5 , K ‾ 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n ) } , if 5 p − 4 ≤ n ≤ 6 p − 6 , { K ‾ 2 ∪ T ‾ n − 2 , p − 1 } , n ≥ 6 p − 5. \overline{\operatorname{EX}}(n, 3\overline{K}_p) = \begin{cases} \overline{K}_{5,6}(n), & \text{if } 3p+1 \le n \le5p-5, \\ \overline{K}_{5,6}(n) \cup\{K^{*}_{5,6}(n)\}, & \text{if } 5p-4 \le n \le6p-6, \\ \{\overline{K}_2 \cup\overline{T}_{n-2,p-1}\}, & n \ge6p-5. \end{cases} EX ( n , 3 K p ) = ⎩ ⎨ ⎧ K 5 , 6 ( n ) , K 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n )} , { K 2 ∪ T n − 2 , p − 1 } , if 3 p + 1 ≤ n ≤ 5 p − 5 , if 5 p − 4 ≤ n ≤ 6 p − 6 , n ≥ 6 p − 5.
Proof. Let G n ∈ EX ‾ ( n , 3 K ‾ p ) G_n \in\overline{\operatorname{EX}}(n, 3\overline{K}_p) G n ∈ EX ( n , 3 K p ) e ∈ E ( G n ) e \in E(G_n) e ∈ E ( G n ) G n G_n G n K ‾ p \overline{K}_p K p G n − e G_n-e G n − e K ‾ p \overline{K}_p K p G n G_n G n K ‾ p \overline{K}_p K p n ≥ 6 p − 5 n \ge6p-5 n ≥ 6 p − 5 EX ‾ ( n , 3 K ‾ p ) = { K ‾ 2 ∪ T ‾ n − 2 , p − 1 } \overline{\operatorname{EX}}(n, 3\overline{K}_p) = \{\overline{K}_2 \cup\overline{T}_{n-2,p-1}\} EX ( n , 3 K p ) = { K 2 ∪ T n − 2 , p − 1 }
Then we consider 3 p + 1 ≤ n ≤ 6 p − 6 3p+1 \le n \le6p-6 3 p + 1 ≤ n ≤ 6 p − 6 G n ∈ K ‾ 5 , 6 ( n ) G_n \in\overline{K}_{5,6}(n) G n ∈ K 5 , 6 ( n ) G n = x ′ K ‾ 5 ∪ y ′ K ‾ 6 ∪ K ‾ 1 , 5 G_n = x'\overline{K}_5 \cup y'\overline{K}_6 \cup\overline{K}_{1,5} G n = x ′ K 5 ∪ y ′ K 6 ∪ K 1 , 5 10 x ′ + 15 y ′ + 5 = 5 ( n − 3 p + 1 ) 10x' + 15y' + 5 = 5(n-3p+1) 10 x ′ + 15 y ′ + 5 = 5 ( n − 3 p + 1 ) 5 x ′ + 6 y ′ + 6 = n 5x' + 6y' + 6 = n 5 x ′ + 6 y ′ + 6 = n x ′ = 6 p − 6 − n x' = 6p-6-n x ′ = 6 p − 6 − n y ′ = n − 5 p + 4 y' = n-5p+4 y ′ = n − 5 p + 4 G n = K 5 , 6 ∗ ( n ) G_n = K^{*}_{5,6}(n) G n = K 5 , 6 ∗ ( n ) K ‾ 5 , 6 ( n ) ⊆ EX ‾ ( n , 3 K ‾ p ) \overline{K}_{5,6}(n) \subseteq\overline{\operatorname{EX}}(n, 3\overline{K}_p) K 5 , 6 ( n ) ⊆ EX ( n , 3 K p ) K 5 , 6 ∗ ( n ) ∈ EX ‾ ( n , 3 K ‾ p ) K^{*}_{5,6}(n) \in\overline{\operatorname{EX}}(n, 3\overline{K}_p) K 5 , 6 ∗ ( n ) ∈ EX ( n , 3 K p )
Claim 10.5. (i) If c = 0 c = 0 c = 0 H 1 ( n ) = { G ∈ K 3 , 4 ( n , q − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } \mathcal{H}_1(n) = \{G \in\mathcal{K}_{3,4}(n,q-1) : \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 3(s+r)\} H 1 ( n ) = { G ∈ K 3 , 4 ( n , q − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} c ≤ 1 c \le1 c ≤ 1 H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s } \mathcal{H}_2(n) = \{G \in\mathcal{K}_{5,6}(n,r-1) : \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 5s\} H 2 ( n ) = { G ∈ K 5 , 6 ( n , r − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 5 s }
Proof. To prove (i), suppose that c = 0 c = 0 c = 0
H 1 ( n ) ⊆ { G ∈ K 3 , 4 ( n , q − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } . (32) \mathcal{H}_1(n) \subseteq\{G \in\mathcal{K}_{3,4}(n,q-1) : \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 3(s+r)\}. \tag*{(32)} H 1 ( n ) ⊆ { G ∈ K 3 , 4 ( n , q − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} . (32) If H 1 ( n ) = ∅ \mathcal{H}_1(n) = \varnothing H 1 ( n ) = ∅ H 1 ( n ) ≠ ∅ \mathcal{H}_1(n) \ne\varnothing H 1 ( n ) = ∅ G 1 ( n ) ∈ H 1 ( n ) G_1(n) \in\mathcal{H}_1(n) G 1 ( n ) ∈ H 1 ( n ) G 1 ( n ) ∈ EX ‾ ( n , K p ∪ K q ) G_1(n) \in\overline{\operatorname{EX}}(n, K_p \cup K_q) G 1 ( n ) ∈ EX ( n , K p ∪ K q ) n ≤ 4 ( p − 1 ) − 1 n \le4(p-1)-1 n ≤ 4 ( p − 1 ) − 1 e ( G 1 ( n ) ) = min { 5 s , 3 ( s + r ) , t ‾ n , p − 1 } e(G_1(n)) = \min\{5s, 3(s+r), \overline{t}_{n,p-1}\} e ( G 1 ( n )) = min { 5 s , 3 ( s + r ) , t n , p − 1 } e ( G 1 ( n ) ) ≥ 3 ( s + r ) e(G_1(n)) \ge3(s+r) e ( G 1 ( n )) ≥ 3 ( s + r ) e ( G 1 ( n ) ) = 3 ( s + r ) e(G_1(n)) = 3(s+r) e ( G 1 ( n )) = 3 ( s + r ) G 1 ( n ) = x K 3 ∪ y K 4 ∪ K ‾ n − 3 x − 4 y G_1(n) = xK_3 \cup yK_4 \cup\overline{K}_{n-3x-4y} G 1 ( n ) = x K 3 ∪ y K 4 ∪ K n − 3 x − 4 y x + y ≥ q x+y \ge q x + y ≥ q
α ( G 1 ( n ) ) = ( x + y ) + ( n − 3 x − 4 y ) = n − ( x + 2 y ) − ( x + y ) ≤ n − ( n − p − q + 1 ) − q = p − 1 , \alpha(G_1(n)) = (x+y) + (n-3x-4y) = n-(x+2y)-(x+y) \le n-(n-p-q+1)-q = p-1, α ( G 1 ( n )) = ( x + y ) + ( n − 3 x − 4 y ) = n − ( x + 2 y ) − ( x + y ) ≤ n − ( n − p − q + 1 ) − q = p − 1 , contradicting the fact that G 1 ( n ) G_1(n) G 1 ( n ) K ‾ p \overline{K}_p K p x + y ≤ q − 1 x+y \le q-1 x + y ≤ q − 1
Next, we prove that
{ G ∈ K 3 , 4 ( n , q − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } ⊆ H 1 ( n ) . (33) \{G \in\mathcal{K}_{3,4}(n,q-1) : \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 3(s+r)\} \subseteq\mathcal{H}_1(n). \tag*{(33)} { G ∈ K 3 , 4 ( n , q − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} ⊆ H 1 ( n ) . (33) Suppose now that ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 3(s+r) ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) K 3 , 4 ( n , q − 1 ) = ∅ \mathcal{K}_{3,4}(n,q-1) = \varnothing K 3 , 4 ( n , q − 1 ) = ∅ K 3 , 4 ( n , q − 1 ) ≠ ∅ \mathcal{K}_{3,4}(n,q-1) \ne\varnothing K 3 , 4 ( n , q − 1 ) = ∅ G ′ = x K 3 ∪ y K 4 ∪ K ‾ n − 3 x − 4 y ∈ K 3 , 4 ( n , q − 1 ) G' = xK_3 \cup yK_4 \cup\overline{K}_{n-3x-4y} \in\mathcal{K}_{3,4}(n,q-1) G ′ = x K 3 ∪ y K 4 ∪ K n − 3 x − 4 y ∈ K 3 , 4 ( n , q − 1 ) x + 2 y = n − p − q + 1 x+2y = n-p-q+1 x + 2 y = n − p − q + 1 x + y ≤ q − 1 x+y \le q-1 x + y ≤ q − 1
α ( G ′ ) = ( x + y ) + ( n − 3 x − 4 y ) = n − ( x + 2 y ) − ( x + y ) ≥ n − ( n − p − q + 1 ) − ( q − 1 ) = p . \alpha(G') = (x+y) + (n-3x-4y) = n-(x+2y)-(x+y) \ge n-(n-p-q+1)-(q-1) = p. α ( G ′ ) = ( x + y ) + ( n − 3 x − 4 y ) = n − ( x + 2 y ) − ( x + y ) ≥ n − ( n − p − q + 1 ) − ( q − 1 ) = p . Thus G ′ G' G ′ K ‾ p \overline{K}_p K p G ′ G' G ′ K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q e ( G ′ ) = 3 ( s + r ) e(G') = 3(s+r) e ( G ′ ) = 3 ( s + r ) G ′ ∈ EX ‾ ( n , K p ∪ K q ∪ K r ) G' \in\overline{\operatorname{EX}}(n, K_p \cup K_q \cup K_r) G ′ ∈ EX ( n , K p ∪ K q ∪ K r ) G ′ ∈ H 1 ( n ) G' \in\mathcal{H}_1(n) G ′ ∈ H 1 ( n )
To prove (ii) suppose that c ≤ 1 c \le1 c ≤ 1
H 2 ( n ) ⊆ { G ∈ K 5 , 6 ( n , r − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s } . (34) \mathcal{H}_2(n) \subseteq\{G \in\mathcal{K}_{5,6}(n,r-1) : \overline{\operatorname{ex}}(n, K_p \cup K_q \cup K_r) = 5s\}. \tag*{(34)} H 2 ( n ) ⊆ { G ∈ K 5 , 6 ( n , r − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 5 s } . (34) If H 2 ( n ) = ∅ \mathcal{H}_2(n) = \varnothing H 2 ( n ) = ∅ H 2 ( n ) ≠ ∅ \mathcal{H}_2(n) \ne\varnothing H 2 ( n ) = ∅ G 2 ( n ) ∈ H 2 ( n ) G_2(n) \in\mathcal{H}_2(n) G 2 ( n ) ∈ H 2 ( n ) G 2 ( n ) ∈ EX ‾ ( n , K p ∪ K q ∪ K r ) G_2(n) \in\overline{\operatorname{EX}}(n, K_p \cup K_q \cup K_r) G 2 ( n ) ∈ EX ( n , K p ∪ K q ∪ K r ) n ≤ 6 ( p − 1 ) + c − 2 n \le6(p-1)+c-2 n ≤ 6 ( p − 1 ) + c − 2 e ( G 2 ( n ) ) ≥ 5 s e(G_2(n)) \ge5s e ( G 2 ( n )) ≥ 5 s e ( G 2 ( n ) ) ≤ 5 s e(G_2(n)) \le5s e ( G 2 ( n )) ≤ 5 s e ( G 2 ( n ) ) = 5 s e(G_2(n)) = 5s e ( G 2 ( n )) = 5 s G 2 ( n ) = x K 5 ∪ y K 6 ∪ K ‾ n − 5 x − 6 y G_2(n)=xK_5\cup yK_6\cup\overline{K}_{n-5x-6y} G 2 ( n ) = x K 5 ∪ y K 6 ∪ K n − 5 x − 6 y x + y ≥ r x+y\ge r x + y ≥ r G 2 ( n ) G_2(n) G 2 ( n )
2 ( x + y ) + ( n − 5 x − 6 y ) = n − ( 2 x + 3 y ) − ( x + y ) ≤ n − ( n − p − q − r + 1 ) − r = p + q − 1. 2(x+y)+(n-5x-6y)=n-(2x+3y)-(x+y)\le n-(n-p-q-r+1)-r=p+q-1. 2 ( x + y ) + ( n − 5 x − 6 y ) = n − ( 2 x + 3 y ) − ( x + y ) ≤ n − ( n − p − q − r + 1 ) − r = p + q − 1. contradicting the fact that G 2 ( n ) G_2(n) G 2 ( n ) K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q x + y ≤ r − 1 x+y\le r-1 x + y ≤ r − 1 (34) .
Next, we prove that
{ G ∈ K 5 , 6 ( n , r − 1 ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s } ⊆ H 2 ( n ) . (35) \{G\in\mathcal{K}_{5,6}(n,r-1):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=5s\}\subseteq\mathcal{H}_2(n). \tag*{(35)} { G ∈ K 5 , 6 ( n , r − 1 ) : ex ( n , K p ∪ K q ∪ K r ) = 5 s } ⊆ H 2 ( n ) . (35) Suppose now that ex ‾ ( n , K p ∪ K q ∪ K r ) = 5 s \overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=5s ex ( n , K p ∪ K q ∪ K r ) = 5 s K 5 , 6 ( n , r − 1 ) = ∅ \mathcal{K}_{5,6}(n,r-1)=\varnothing K 5 , 6 ( n , r − 1 ) = ∅ (35) holds. If K 5 , 6 ( n , r − 1 ) ≠ ∅ \mathcal{K}_{5,6}(n,r-1)\ne\varnothing K 5 , 6 ( n , r − 1 ) = ∅ G ′ = x K 5 ∪ y K 6 ∪ K ‾ n − 5 x − 6 y ∈ K 5 , 6 ( n , r − 1 ) G'=xK_5\cup yK_6\cup\overline{K}_{n-5x-6y}\in\mathcal{K}_{5,6}(n,r-1) G ′ = x K 5 ∪ y K 6 ∪ K n − 5 x − 6 y ∈ K 5 , 6 ( n , r − 1 ) 2 x + 3 y = n − p − q − r + 1 2x+3y=n-p-q-r+1 2 x + 3 y = n − p − q − r + 1 x + y ≤ r − 1 x+y\le r-1 x + y ≤ r − 1 G ′ G' G ′
2 ( x + y ) + ( n − 5 x − 6 y ) = n − ( 2 x + 3 y ) − ( x + y ) ≥ n − ( n − p − q − r + 1 ) − ( r − 1 ) = p + q . 2(x+y)+(n-5x-6y)=n-(2x+3y)-(x+y)\ge n-(n-p-q-r+1)-(r-1)=p+q. 2 ( x + y ) + ( n − 5 x − 6 y ) = n − ( 2 x + 3 y ) − ( x + y ) ≥ n − ( n − p − q − r + 1 ) − ( r − 1 ) = p + q . Thus G ′ G' G ′ K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q Lemma 9.2 , G ′ G' G ′ K ‾ p \overline{K}_p K p K ‾ q \overline{K}_q K q K ‾ r \overline{K}_r K r e ( G ′ ) = 5 s e(G')=5s e ( G ′ ) = 5 s G ′ ∈ E X ( n , K p ∪ K q ∪ K r ) G'\in\mathrm{EX}(n,K_p\cup K_q\cup K_r) G ′ ∈ EX ( n , K p ∪ K q ∪ K r ) G ′ ∈ H 2 ( n ) G'\in\mathcal{H}_2(n) G ′ ∈ H 2 ( n ) (35) . □
Now we are ready to finish the proof of the theorem.
Case 1: c = 0 c=0 c = 0 H 0 ( n ) ⊆ E X ( n , K p ) \mathcal{H}_0(n)\subseteq\mathrm{EX}(n,K_p) H 0 ( n ) ⊆ EX ( n , K p ) H 0 ( n ) = { T ‾ n , p − 1 : ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n , p − 1 } \mathcal{H}_0(n)=\{\overline{T}_{n,p-1}:\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\overline{t}_{n,p-1}\} H 0 ( n ) = { T n , p − 1 : ex ( n , K p ∪ K q ∪ K r ) = t n , p − 1 }
Case 2: c = 1 c=1 c = 1 Claim 10.1 (i), H 0 ( n ) = ∅ \mathcal{H}_0(n)=\varnothing H 0 ( n ) = ∅ H 1 ( n ) ⊆ E X ( n , 2 K p ) \mathcal{H}_1(n)\subseteq\mathrm{EX}(n,2K_p) H 1 ( n ) ⊆ EX ( n , 2 K p )
H 1 ( n ) = { G ∈ K 3 , 4 ( n ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) } ∪ { K 3 , 4 ∗ ( n ) : ex ‾ ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) and 3 ( p + q ) 2 − 2 ≤ n ≤ 2 p + 2 q − 4 } ∪ { K ‾ 1 ∪ T ‾ n − 1 , p − 1 : ex ‾ ( n , K p ∪ K q ∪ K r ) = t ‾ n − 1 , p − 1 } . \begin{aligned}
\mathcal{H}_1(n)={}&\{G\in\mathcal{K}_{3,4}(n):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=3(s+r)\}\\
&\cup\{K^*_{3,4}(n):\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=3(s+r)\text{ and }\frac{3(p+q)}{2}-2\le n\le2p+2q-4\}\\
&\cup\{\overline{K}_1\cup\overline{T}_{n-1,p-1}:\overline{\operatorname{ex}}(n,K_p\cup K_q\cup K_r)=\overline{t}_{n-1,p-1}\}.
\end{aligned} H 1 ( n ) = { G ∈ K 3 , 4 ( n ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r )} ∪ { K 3 , 4 ∗ ( n ) : ex ( n , K p ∪ K q ∪ K r ) = 3 ( s + r ) and 2 3 ( p + q ) − 2 ≤ n ≤ 2 p + 2 q − 4 } ∪ { K 1 ∪ T n − 1 , p − 1 : ex ( n , K p ∪ K q ∪ K r ) = t n − 1 , p − 1 } . By Claim 10.5(ii), we are done.
Case 3: c = 2 c=2 c = 2 r = q = p r=q=p r = q = p Claim 10.1 , H 0 ( n ) = ∅ \mathcal{H}_0(n)=\varnothing H 0 ( n ) = ∅ H 1 ( n ) = ∅ \mathcal{H}_1(n)=\varnothing H 1 ( n ) = ∅ H 2 ( n ) = E X ( n , 3 K p ) \mathcal{H}_2(n)=\mathrm{EX}(n,3K_p) H 2 ( n ) = EX ( n , 3 K p )
H 2 ( n ) = { K 5 , 6 ( n ) , if n ≤ 5 p − 5 , K 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n ) } , if 5 p − 4 ≤ n ≤ 6 p − 6 , { K ‾ 2 ∪ T ‾ n − 2 , p − 1 } , n ≥ 6 p − 5. \mathcal{H}_2(n)=
\begin{cases}
\mathcal{K}_{5,6}(n), & \text{if }n\le5p-5,\\
\mathcal{K}_{5,6}(n)\cup\{K^*_{5,6}(n)\}, & \text{if }5p-4\le n\le6p-6,\\
\{\overline{K}_2\cup\overline{T}_{n-2,p-1}\}, & n\ge6p-5.
\end{cases} H 2 ( n ) = ⎩ ⎨ ⎧ K 5 , 6 ( n ) , K 5 , 6 ( n ) ∪ { K 5 , 6 ∗ ( n )} , { K 2 ∪ T n − 2 , p − 1 } , if n ≤ 5 p − 5 , if 5 p − 4 ≤ n ≤ 6 p − 6 , n ≥ 6 p − 5. □
Concluding remarks
We think that the following claims are likely to be true.
Conjecture 1. Let k 1 , k 2 , … , k ℓ − 1 ≥ k ℓ ≥ 2 k_1,k_2,\ldots,k_{\ell-1}\ge k_\ell\ge2 k 1 , k 2 , … , k ℓ − 1 ≥ k ℓ ≥ 2 n ≥ k 1 + k 2 + ⋯ + k ℓ n\ge k_1+k_2+\cdots+k_\ell n ≥ k 1 + k 2 + ⋯ + k ℓ s = n − k 1 − k 2 − ⋯ − k ℓ + 1 s=n-k_1-k_2-\cdots-k_\ell+1 s = n − k 1 − k 2 − ⋯ − k ℓ + 1 n n n G G G K ‾ k 1 , … , K ‾ k ℓ − 1 \overline{K}_{k_1},\ldots,\overline{K}_{k_{\ell-1}} K k 1 , … , K k ℓ − 1 e ( G ) < ( 2 ℓ − 1 ) s e(G)<(2\ell-1)s e ( G ) < ( 2 ℓ − 1 ) s G G G K ‾ k 1 , … , K ‾ k ℓ \overline{K}_{k_1},\ldots,\overline{K}_{k_\ell} K k 1 , … , K k ℓ
Conjecture 2. Let ℓ ≥ 4 \ell\ge4 ℓ ≥ 4 k 1 , k 2 , … , k ℓ k_1, k_2, \ldots, k_\ell k 1 , k 2 , … , k ℓ k 1 ≥ k 2 ≥ … ≥ k ℓ − 1 ≥ k ℓ ≥ 2 k_1 \ge k_2 \ge\ldots\ge k_{\ell-1} \ge k_\ell\ge2 k 1 ≥ k 2 ≥ … ≥ k ℓ − 1 ≥ k ℓ ≥ 2 t = max { i ∣ k i = k 1 , 1 ≤ i ≤ ℓ } t = \max\{i \mid k_i = k_1, 1 \le i \le\ell\} t = max { i ∣ k i = k 1 , 1 ≤ i ≤ ℓ }
(1) If there is an integer n 3 ≥ k 1 + k 2 + ⋯ + k ℓ n_3 \ge k_1+k_2+\cdots+k_\ell n 3 ≥ k 1 + k 2 + ⋯ + k ℓ K t − 1 ∨ T n 3 − t + 1 , k 1 − 1 ∈ EX ( n 3 , K k 1 ∪ ⋯ ∪ K k ℓ ) K_{t-1} \vee T_{n_3-t+1,k_1-1} \in\operatorname{EX}(n_3, K_{k_1} \cup\cdots\cup K_{k_\ell}) K t − 1 ∨ T n 3 − t + 1 , k 1 − 1 ∈ EX ( n 3 , K k 1 ∪ ⋯ ∪ K k ℓ ) K t − 1 ∨ T n − t + 1 , k 1 − 1 ∈ EX ( n , K k 1 ∪ ⋯ ∪ K k ℓ ) K_{t-1} \vee T_{n-t+1,k_1-1} \in\operatorname{EX}(n, K_{k_1} \cup\cdots\cup K_{k_\ell}) K t − 1 ∨ T n − t + 1 , k 1 − 1 ∈ EX ( n , K k 1 ∪ ⋯ ∪ K k ℓ ) n ≥ n 3 n \ge n_3 n ≥ n 3
(2) If there is an integer n 4 ≥ k 1 + k 2 + ⋯ + k ℓ n_4 \ge k_1+k_2+\cdots+k_\ell n 4 ≥ k 1 + k 2 + ⋯ + k ℓ EX ( n 4 , K k 1 ∪ ⋯ ∪ K k ℓ ) = { K t − 1 ∨ T n 4 − t + 1 , k 1 − 1 } \operatorname{EX}(n_4, K_{k_1} \cup\cdots\cup K_{k_\ell}) = \{K_{t-1} \vee T_{n_4-t+1,k_1-1}\} EX ( n 4 , K k 1 ∪ ⋯ ∪ K k ℓ ) = { K t − 1 ∨ T n 4 − t + 1 , k 1 − 1 } EX ( n , K k 1 ∪ ⋯ ∪ K k ℓ ) = { K t − 1 ∨ T n − t + 1 , k 1 − 1 } \operatorname{EX}(n, K_{k_1} \cup\cdots\cup K_{k_\ell}) = \{K_{t-1} \vee T_{n-t+1,k_1-1}\} EX ( n , K k 1 ∪ ⋯ ∪ K k ℓ ) = { K t − 1 ∨ T n − t + 1 , k 1 − 1 } n ≥ n 4 n \ge n_4 n ≥ n 4
Acknowledgment
Part of the work was carried out while the third author was a PhD student at the University of Illinois Urbana-Champaign and was supported in part by NSF RTG Grant DMS-1937241.
University of Illinois at Urbana–Champaign, Urbana, IL 61801 Email address: kostochk@illinois.edu
University of Illinois at Urbana–Champaign, Urbana, IL 61801 Email address: dadongp2@illinois.edu
Shanghai Center for Mathematical Sciences, Fudan University, Shanghai 200433, P.R.China Email address: zimuxiang@fudan.edu.cn
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P.R.China. Email address: 1120240010@mail.nankai.edu.cn
