G和H均为简单图.G+H表示通过G和H之间完全连边所得到的图.如果V(H)⊆V(G)，G∨H表示把H中不属于E(G)的边添加到G中所得到的图.如果H是G的子图，G－H表示从图G中删掉H的边所得到的图.G\H表示从图G中删掉图H的点和边所得到的图.N(v)和d(v)分别表示顶点v的邻域和度数.N_G^R(v)和d_G^R(v)分别为顶点v在图G中的红邻域和红度，同理N_G^B(v)和d_G^B(v)为G中顶点v的蓝邻域和蓝度.

1 研究内容

设G和H是任意的2个图.Ramsey数r(G, H)定义为最小的正整数r，使得图K_r的任意红蓝边着色存在红色子图G或蓝色子图H.实际上，在Ramsey数的实际研究中，发现完全图K_r在删掉某些边后仍然可能存在红色子图G或蓝色子图H.Hook和Isaak首先在文献[1]中提出临界星图Ramsey数r_*(G, H)为最小的正整数n，使得K_r－K_{1, r-1-n}的任意红蓝边着色或存在单色的红色子图G，或存在单色的蓝色子图H.Hook和Isaak在文献[1]以及Hook在文献[2]和文献[3]中确定了r_*(T_n, K_m)=(n－1)(m－2)+1，r_*(nK₂, mK₂)=m, n≥m≥1，r_*(P_n, C₄)=3, n≥3和r_*(P_n, P_m)=$\left\lceil { m/2} \right\rceil $, n≥m≥4等临界星图Ramsey数.

在完全图K_r中寻找删掉最大完全图使得导出子图中存在红色子图G或蓝色子图H的最大完全图的阶数，此最大阶数定义为临界完全图Ramsey数r_K(G, H).

定义1   设r(G, H)为Ramsey数，临界完全图Ramsey数为最大的正整数n，使得图K_r－K_n的任意红蓝二边着色或存在单色的红色子图G或存在单色的蓝色子图H.

定理1   当整数n≥5时，r_K(C_n, K₄)=$\left\lfloor { n/2} \right\rfloor $；n=4时，r_K(C₄, K₄)=2.

2 主要结果的证明

引理1^[4]   当整数n≥4时，r(C_n, K₄)=3n－2.

引理2^[2]  当整数n≥5时，临界星图Ramsey数r_*(C_n, K₄)=2n.

定理1的证明。n=4时，r(C₄, K₄)=10，根据r(W_{1, 6}, K₄)=9可知K₉中若不存在红色K₄与蓝色C₄必存在蓝色3C₃，即可证K₁₀－K₂中存在红色K₄或蓝色C₄.则r_K(C₄, K₄)=2.

n≥5时，由于n为奇数时证明与偶数类似，所以只证明偶数情况.当n为偶数, 考虑图G=K_3n－2－K_n/2+1.令G₁=K_{n－1, n－1, n/2－1}为蓝色三部图，其点集为V(G₁)=C₁∪C₂∪C₃, C_i, i=1, 2, 3为红色团.G₂=(n/2+1)K₁与C₁、C₂连蓝边，C₃连红边.G不存在红色的C_n与蓝色的K₄.所以r_K(C_n, K₄)≤$\left\lfloor { n/2} \right\rfloor $.

现只需证明r_K(C_n, K₄)≥$\left\lfloor { n/2} \right\rfloor $.证明采用归纳假设法.n=5，r(C₅, K₄)=13，r_*(C₅, K₄)=10，则r_K(C₅, K₄)=2.假设当n≥6时，r_K(C_n－1, K₄)=$\left\lfloor { (n-1)/2} \right\rfloor $.考虑图G=K_3n－2－K_n/2，即K_5n/2－2∨n/2K₁.假设任意红蓝边着色下G不存在红色C_n和蓝色K₄.令G₁=K_5n/2－2，G₂=n/2K₁.证明需要引入引理3.

引理3   当整数n≥6时，若图G=K_3n－2－K_n/2中不存在红色C_n但存在红色C_n－1，且G₁\C_n－1中存在蓝色K₃，此时G₁中必可找到蓝色K₄.

证明   设C_n－1=a₀…a_n－2，A={a_i|a_i+1∈G₁}，B={a_i|a_i+1∈G₂}，可知|A|≥n/2.若C_n－1∩G₂=∅，Hook在文献[2]中已证明引理3成立.假设|C_n－1∩G₂|≥1且G₁\C_n－1中存在蓝色K₃=u₁u₂u₃.d_A^R(u_i)≤2，i=1, 2, 3.若不然令边u_ia_i、u_ia_j、u_ia_k为红边，u_ia_i+1、u_ia_j+1、u_ia_k+1为蓝边，i < j < k.a_i+1a_j+1a_k+1中若存在一条红边则产生红色C_n，a_i+1a_j+1a_k+1为蓝色K₃与u_i一起构成蓝色K₄，矛盾.同理若d_A^R(u_i)=2，则d_B^R(u_i)=0.

(1) 情形1.若d_A^R(u_i)=2，i=1, 2, 3, 有d_B^R(u_i)=0.因为B≠∅，所以B中存在一点与u₁u₂u₃连蓝边，构成蓝色K₄.

(2) 情形2.若d_A^R(u₁)=1，d_A^R(u_i)=2，i=2, 3.有d_B^R(u_i)=0，i=2, 3.当n≥12时，|A|≥6，此时A中存在一点与u₁u₂u₃连蓝边，构成蓝色K₄.当n=10时，为避免蓝色K₄，|A|=n/2，|B|=n/2－1且N_A^R(u_i)∩N_A^R(u_j)=∅，i, j=1, 2, 3，i≠j.因此|C_n－1∩G₁|=n/2，|C_n－1∩G₂|=n/2－1.u_i(i=2, 3)与B全连蓝边，u₁与B全连红边，d_A^R(u₁)=1使得u₁与C_n－1中某相邻两点连红边，形成红色C_n，与假设矛盾.n=6, 8时证明类似.

(3) 情形3.若d_A^R(u_i)=1，d_A^R(u₃)=2，i=1, 2, 有d_B^R(u₃)=0.同理，当n≥10时，|A|≥5，此时A存在一点与u₁u₂u₃连蓝边形成蓝色K₄.所以n=8时，|A|=4，|B|=3且N_A^R(u_i)∩N_A^R(u_j)=∅，i≠j，i, j=1, 2, 3.因此|C_n－1∩G₁|=4，|C_n－1∩G₂|=3.设A={a₀, a₁, a₂, a₃}，B={b₀, b₁, b₂}，C₇=b₀a₀b₁a₁b₂a₂a₃b₀.因d_A^R(u₁)=d_A^R(u₂)=1，令u₁a₀、u₂a₁为红边，此时u₃a₂、u₃a₃为红边形成红色C_n.令u₁a₀、u₂a₂为红边，此时u₃a₁、u₃a₃为红边，u₁a₂、u₃a₂为蓝边.注意到u₁b₀、u₁b₁、u₂b₂、u₃b₀、u₃b₁、u₃b₂为蓝边否则产生红色C_n.为避免蓝色K₄, b₀a₂、u₁b₂、u₂b₁为红边，C_n=b₀a₀u₁b₂a₁b₁u₂a₂b₀.令u₁a₀、u₂a₃为红边，b₀u₁u₂u₃形成蓝色K₄.令u₁a₁、u₂a₂为红边，b₂u₁u₂u₃形成蓝色K₄.令u₁a₁、u₂a₃为红边，u₃a₃、u₁b₁、u₃b₁为蓝边.且u₁a₃为蓝边，若u₁a₃为红边则产生红色.若b₁a₃是蓝边，则b₁a₃u₃u₁为蓝色K₄；若b₁a₃是红边，则C_n=b₀a₀u₃a₂b₂a₁b₁a₃b₀，矛盾.令u₁a₂、u₂a₃为红边，则u₁a₃、u₁b₂、u₂b₀、u₃b₀、u₃b₁、u₃b₂为蓝边.则u₁b₀、u₂b₂为红边否则产生蓝色K₄.b₁b₂为蓝边，u₁b₁为红边否则产生红色C_n.n=6时证明类似.

(4) 情形4.若d_A^R(u_i)=1，i=1, 2, 3.当n≥8时同情形2.n=6，且|A|=3，|B|=2.N_A^R(u_i)∩N_A^R(u_j)=∅，i, j=1, 2, 3, i≠j.|C_n－1∩G₁|=3，|C_n－1∩G₂|=2.设A={a₀, a₁, a₂}，B={b₀, b₁}，C₅=b₀a₀b₁a₁a₂b₀.因为d_A^R(u_i)=1，令u₁a₀、u₂a₁、u₃a₂为红边，则u₁b₀、u₁b₁、u₂b₁、u₃b₀为蓝边，为避免蓝色K₄，u₂b₀、u₃b₁为红边，产生C₆=b₀u₂a₁b₁u₃a₂b₀，矛盾.

(5) 情形5.存在u_i使得d_A^R(u_i)=0, 证明类似.

至此已证明引理3，为证明定理1还需要一些说明.|G₁|=5n/2－2≥r(C_n, K₃)=2n－1，n≥6.所以G₁存在蓝色K₃=u₁u₂u₃.令H=G\K₃=K_5n/2－5∨n/2K₁.如果图H中可找到红色C_n－1，根据引理3与假设矛盾，定理得证.以下假设H的任意红蓝染色不存在红色C_n－1与蓝色K₄.根据归纳假设，r_K(C_n－1, K₄)=$\left\lfloor { (n-1)/2} \right\rfloor $，K_5n/2－4∨(n－2)/2K₁的任意红蓝染色一定存在红色C_n－1或蓝色K₄.H∨{u₃}=K_5n/2－4∨n/2K₁，因为假设图G不存在蓝色K₄，则H∨{u₃}的任意红蓝染色一定存在红色C=C_n－1，所以在每种红蓝染色中此红色圈必定包含点u₃，否则与H中不存在红色C_n－1的假设矛盾.令u₃在C中的邻居为a₀、a₁，由引理3，在G₁\C中不存在蓝色K₃，在G\K₃中不存在红色C_n－1, 因此N_G^R(a₀)∩N_G^R(a₁)=∅.令F=G₁\{u₁, u₂}，N₁=N_F^R(a₀)∩N_F^B(a₁)，N₂=N_F^B(a₀)∩N_F^R(a₁)，N₃=N_F^B(a₀)∩N_F^B(a₁).令C=a₀u₃a₂…a_n－2，设a₁的位置为u₃.令A={a_i|a_i+1∈G₁}，B={a_i|a_i+1∈G₂}.

引理4   对完全图K_s任意红蓝染色，s≥n+1，n≥6，若图K_s存在红色哈密顿圈且不存在红色C_n－1与红色C_n，则K_s中存在蓝色K₃；若图K_s中存在红色哈密顿路(不存在红色哈密顿圈)且不存在红色C_n－1、红色C_n与蓝色K₃，则K_s的红色生成子图为2个连通的红团.

证明   若图K_s中存在红色哈密顿圈，设为C_s=c₁c₂…c_s.反证假设图K_s不存在蓝色K₃.因为不存在红色C_n－1与红色C_n，所以c₁c_n－1、c₁c_n、c₂c_n、c₂c_n+1、c₃c_n+1为蓝边.c₃c_n若为红边，则c₃c₄…c_n－1c_nc₃为红圈C_n－2，若d_Cn－2^R(c₂)≥2，设c₂c_i、c₂c_j, i < j为红边，则c₂c_i+1、c₂c_j+1为蓝边，若c_i+1c_j+1为红边则产生红圈C_n，则可找到蓝色K₃，引理得证.则d_Cn－2^R(c₂)≤1，d_Cn－2^R(c_n+1)≤1，N_Cn－2^B(c₂)∩N_Cn－2^B(c_n+1)≠∅，存在蓝色K₃，因此c₃c_n为蓝边.若c₃c₁为蓝边则c₃c_nc₁为蓝色K₃, 与假设矛盾.c₃c₁为红边，则C_s变为长度减1的圈C_s－1.继续上述步骤，因为s≥n+1，若不存在蓝色K₃即可找到红色C_n.

若图K_s中存在红色哈密顿路(不存在红色哈密顿圈)，设为D_s=d₁d₂…d_s，d₁d_s为蓝边.因为存在红色哈密顿圈且不存在红色C_n－1与红色C_n，可找到蓝色K₃，所以d₁d_n－1, d₁d_n, …, d₁d_s, d₂d_n、d₂d_n+1, …, d₂d_s、d₃d_n+1, …, d₃d_s均为蓝边.注意必有d_id₁或d_id_s, i=2, …, s－1红边，否则产生蓝色K₃与假设矛盾.若d_id_s为红边，d_i+1d_s, …, d_s－1d_s, 均为红边，d_i+1d₁, …, d_s－1d₁均为蓝边，否则会产生红色哈密顿圈，产生蓝色K₃.若d_jd_s为红边，d_j－1d₁, …, d₂d₁均为红边，d_j－1d_s, …, d₂d_s均为蓝边，注意到i=j或i=j+1.因K_s不存在蓝色K₃所以d_id_i+1…d_s与d_jd_j－1…d₁为连通红团，引理得证.

至此已证明引理4.在引理4第二部分的证明中，除去d_i与d_j外两红团全连蓝边，否则会产生红色C_n.

事实1   N₃≠∅.

反证假设N₃=∅.若N₃=∅、N₁≠∅、N₂≠∅.N₁与N₂完全连蓝边，否则产生红色C_n.由于G₁\C不存在蓝色K₃，因此N₁与N₂为红团且u₃与N₁、N₂连蓝边.|N₁+N₂|≥3n/2－3，因为|N₂|≤n－3，否则|N₂∪a₁|≥n－1，所以|N₁|≥n/2，d_C\{a0}^R(v)=0, ∀v∈N₁，若d_C^R(v)≥1，N₁与C存在红色C_n.同理d_C\{a1}^R(v)=0, ∀v∈N₂.因此C\{a₀, a₁}不存在蓝边.则∀v∈G₂\C，d_C∩G1^R(v)≤1, d_C∩G1^B(v)≥1，且v、u₁、u₂与N₁、N₂至少一个全连红边，|G\C|=2n－1，根据鸽巢原理，N₁、N₂、G₁\C中会产生红色C_n.

若N₃=∅, N₁≠∅, N₂=∅(N₁=∅, N₂≠∅与情形2相同).此时u₃与N₁全连蓝边.设N₁中的最长红路为Q=q₁q₂…q_l.N₁\Q≠∅，否则|N₁|≥3n/2－3，与a₁构成红色C_n.由于Q的极大性，q₁、q_l与N₁\Q连蓝边，又因G₁\C不存在蓝色K₃，q₁q_l为红边，则Q与N₁\Q全连蓝边且Q与N₁\Q为红团.同理N₁与C\{a₁}中点全连蓝边，C中不存在蓝边，u₁、u₂与Q，N₁\Q至少一个全连红边，|G\C|=2n－1根据鸽巢原理，产生红色C_n.

因为N₃≠∅，总能在N₃中找到最长红路设为P=p₁p₂…p_m，若N₃\P≠∅，同理P与N₃\P为红色团且之间全连蓝边.

事实2   N₁=∅, N₂=∅.

情形1.反证假设N₁≠∅、N₂≠∅.若N₃\P=∅，N₃中可找到红色哈密顿路设为P=p₁p₂…p_m.G₁\C不存在蓝色K₃，所以d_N1^B(p₁)=0与d_N2^B(p₁)=0至少一个成立，p_m同理.若d_N1^R(p₁)≥1, d_N2^R(p_m)≥1，根据引理4，G₁\C为2个连通红团，N₁与N₂全连蓝边，分别属于2个红团，则a₀u₃a₁N₂·p_m…p₁N₁中存在红色C_n.设d_N1^B(p₁)=d_N1^B(p_m)=0，d_N2^B(p₁)=d_N2^B(p_m)=|N₂|，p₁p_m为红边否则产生蓝色K₄，N₃与N₂全连蓝边与N₁全连红边.N₃为红团，N₁与N₂全连蓝边.∀v∈N₂，d_C\{a1}^R(v)=0，∀v∈N₃, d_C^R(v)≤1，|N_C^R(N₃)|≤1.若|N₁|≥2，∀v∈N₁，d_C\{a0}^R(v)=0.所以C\{a₂}中无蓝边.∀v∈G₂\C，d_C∩G1^R(v)≤1且v∪{u₁, u₂}与N₁∪N₃或N₂全连红边(|N₁|=1时与N₃或N₂全连红边).|G\C|≥2n－1，产生红色C_n.因此N₃\P≠∅，N₃∪N₁⊆N_G^B(a₂)，N₃∪N₂⊆N_G^B(a₁)，∀v∈N₁∪N₂，d_P^B(v)=0与d_N3\P^B(v)=0至少一个成立，并且∀v∈N₁、u∈N₂，d_P^B(v)=0、d_N3\P^B(u)=0或d_P^B(u)=0、d_N3\P^B(v)=0.不妨令N₁与P全连红边N₂与N₃\P全连红边.N₁∪P与N₂∪{N₃\P}为红团且之间全连蓝边，同理C不存在蓝边.∀v∈G₂\C、d_C∩G1^R(v)≤1、d_C∩G1^B(v)≥1且{v}∪{u₁, u₂}与N₁∪P或N₂∪{N₃\P}全连红边，存在红色C_n.

情形2.假设N₁≠∅、N₂=∅.设N₁中最长红路为Q=q₁q₂…q_l.若N₃\P=∅、N₁\Q≠∅，证明类似.若N₃\P≠∅、N₁\Q≠∅、Q与N₁\Q为红团且全连蓝边，P与N₃\P为红团且全连蓝边.∀v∈N₃，d_Q^B(v)=0与d_N1\Q^B(v)=0至少一个成立，证明同N₁≠∅、N₂≠∅、N₃\P≠∅相同.

若N₃\P≠∅、N₁\Q=∅.P与N₃\P为红团且全连蓝边.此时d_P^B(q_i)=0或d_N3\P^B(q_i)=0，i=1, l成立.若d_P^B(q₁)=0，必有d_P^B(q_l)=0.否则设q₁与P全连红边、q_l与N₃\P全连红边，由引理4，产生红色C_n.令两红团为N₁∪P与N₃\P.因此∀u∈N₁∪P、v∈N₃\P，都有d_C^R(u)≤1、d_C^R(v)≤1.除u₃或a_n－2外，C中无蓝边.则∀v∈G₂\C、d_C∩G1^R(v)≤1、d_C∩G1^B(v)≥1且n≥6时N_C∩G1^B(v)∩N_C∩G1^B(P)∩N_C∩G1^B(N₃\P)≠∅，所以v与N₁∪P或N₃\P全连红边(|N₁|=1时与P或N₃\P全连红边).设q₁、q_l与P全连红边，与N₃\P全连蓝边，q₁q_l为红边.此时N₁是哈密顿的，N₁与P全连红边，同理产生红色C_n.

若N₃\P=∅、N₁\Q=∅，设N₁的红色哈密顿路为Q=q₁q₂…q_l，N₃的红色哈密顿路为P=p₁p₂…p_m.若q₁q_l为蓝边，p₁、p_m与q₁或q_l连红边，不妨设p₁q₁为红边，由引理4产生红色C_n.则q₁q_l为红边，N₁为红团，否则若N₁存在蓝边则可找到红色C_n.d_N1^R(p₁)=0.若d_N1^R(p₁)≥1，由引理4，d_N1^R(p₁)≥2时d_N1^R(p_m)=0；d_N1^R(p₁)=1时d_N1^R(p_m)≤1，N_N1^R(p₁)⊆N_N1^R(p_m).G₁\C为2个连通红团设为R₁、R₃，恰好为N₁与N₃或N₁∪{p₁, …, p_i}与N₃\{p₁, …, p_i}，1≤i≤m－1.N_C^R(R₃)=∅，|N_C^R(R₁\N₁)|≤2，N_C\{a1}^R(N₁)=∅，因此C无蓝边，为避免红色C_n，|N_C^R(R₁\N₁)|≤1.∀v∈G₂\C，d_C∩G1^R(v)≤1.{v}∪{u₁, u₂}与R₁或R₃全连红边产生红色C_n.同理d_N1^R(p_m)=0，p₁p_m为红边，d_N1^R(p_i)=0，i=1, …, m，N₃为红团.同上述证明相同，矛盾.

接下来证明定理1.不妨令B≠∅.假设N₃\P≠∅，则P与N₃\P为红色团且之间全连蓝边.设d_C^R(v₁)≥d_C^R(v₂)≥…≥d_C^R(v_|P|)，∀v_i∈P，d_C^R(u₁)≥d_C^R(u₂)≥…≥d_C^R(u_|N3\P|)，∀u_i∈N₃\P.若d_C^R(v₁)≥2，则d_C^R(v_i)≤1, i=2, …, |P|，N_C^R(v_i)⊆N_C^R(v₂).若d_C^R(v₁)≤1，则d_C^R(v_i)≤1，i=2, …, |P|，N_C^R(v_i)⊆(N_C^R(v₁)∪N_C^R(v₂)).因此∀v_i∈P，d_C^B(v_i)≥n－2, i=2, …, |P|.同理∀u_i∈N₃\P，d_C^B(u_i)≥n－2, i=2, …, |N₃\P|.因此C无蓝边，∀v∈G₂\C，有d_C∩G1^R(v)≤1，N_C∩G1^B(v)∩N_C∩G1^B(P)∩N_C∩G1^B(N₃\P)≠∅.则{v}∪{u₁, u₂}与P或N₃\P全连红边，据鸽巢原理产生红色C_n.若N₃\P=∅，N₃存在红色哈密顿路P=p₁p₂…p_m.N₃不存在红色C_n－1与红色C_n，因为B≠∅，所以n≥6时，N₃≥3n/2－3+1≥n+1.p₁p_m为红边时，根据引理4，N₃中存在蓝色K₃，又因为引理3，G₁中存在蓝色K₄.p₁p_m为蓝边时，根据引理4，N₃为连通红团，同理可找到红色C_n.矛盾，定理得证.

3 结语与展望

提出了临界Ramsey数，推广了经典Ramsey数的概念.在未来的研究中，可以将这个结果推广到r_K(C_n, K_m)，n≥m≥3.进而可以去考虑在图K_r中删掉其他特定图的临界Ramsey数.