图论中的r-圈策略
冯跃峰
本文中所指的r-圈是由r条互异的边构成的一个圈，记为Cr。
众所周知，图论中涉及圈的定理通常只指存在某种圈，但并不能确定圈的具体长度。若要找r-圈，则可采用以下扩充策略。为叙述问题方便，我们先给出如下的
定义：两条有公共顶点的边组成的图称为“2-链”，公共顶点称为2-链的中心，另两个顶点称为2-链的端点。类似定义t-链。
一般地说，寻找图G中的r-圈，有以下4种常用策略。
（1）由一条“2-链”扩充：取2-链ABC，然后由两端点A、C向两边扩展成更长的链，最后在两端点的邻域中找公共点，或邻域中各取一个点相连。
（2）由一条边扩充：取边AB，然后由两端点A、B向两边扩展成更长的链，最后在两端点的邻域中找公共点，或邻域中各取一个点相连。
（3）由中间点扩充：取两个中间点A、B，在边AB（可能是虚边）两侧分别扩充。
（4）由两条t-链拼合：令每条t-链与其两个端点对应，证明有2条t-链对应同一个“2点组”，则这2条t-链拼合成一个长为2t的圈。
值得指出的是，当r不同时，找r-圈的技巧又略有不同，我们以典型的圈C3、C4为例。
找三角形仅有2种常用策略：
（i）由一条“2-链”扩充：取点A为“2-链”中心，证明A的邻域中有2点相邻（通常用到“邻域分块”、“充分条件分类”等技巧）；
（ii）由一条边扩充：适当取边AB，证明两端点A、B的邻域有公共点，即
|D（A）∩D（B）|≥1。
找四边形有4种策略：
（i）由一条“2-链”扩充：取点A为“2-链”中心，证明有一个异于A的点向A的邻域引出两条边（与邻域中两个点相邻）；
（ii）由一条边扩充：取边AB，证明A邻域中一点与B邻域中一点相邻；
（iii）由点对扩充：取两点A、B，证明A、B的邻域有2个公共点，即
|D（A）∩D（B）|≥2；
（4）由两条2-链拼合：令每条2-链与其两个端点对应，证明有两条2-链对应同一个“2点组”，则这两条2-链拼合成一个四边形。
以下用具体例子说明。
例1、若干个城市共派出2n（n≥3）名选手参加桥牌友谊赛，比赛规定：同一个城市的任何2名选手不同在同一局中作为敌我对手进行比赛。如果每个城市都至多派出n名队员，且一个队员可以比赛多次，试证：至少可以安排n（n²-3n 1）局比赛。（原创题）
【题感】由比赛规则看，同一局的4个选手中邻座属于不同的城市，于是想到用点表示选手，将属于不同城市的选手连边，得到一个2n阶简单图G。
问题变成：若每个顶点的度至少是2n-n=n，证明2n阶简单图G中存在n（n²-3n 1）个4-圈。
由目标看，为说明找圈的方法，先先退一步：假定是找“一个”4-圈的问题（见“新写1”与“新写2”），这自然可采用局部扩展策略。在此基础上，最后再解决原问题（见“新写3”）。
先考虑由一条“2-链”扩充的方法，此时需要再找一个点向“2链”中心的邻域引两条边。由此又想到邻域分块技巧。
【邻域分块】“任取”一个点x为“2链”中心，令
A={a|a与x相邻}，B={b|b与x不相邻}，
依题意|A|≥n，|B|≤n-1。
我们只需找到B中一个点b向a的邻域A引出两条边。
这有如下两个问题需要解决：
①B中有点b；②b向a的邻域A引出两条边。
对于问题①，自然想到优化假设，令最先取的点x满足：d（x）<2n-1。但这样的点x未必存在，分类讨论即可。
对于问题②，可采用反面思考：如果B中的点b至多在A中连1条边，则d（b）≤1 dB（b）≤1 （|B|-1）≤1 （n-2）<n，与条件矛盾。
图1
【新写1】若对所有点x，有d（x）=2n-1，则G是完全图，结论显然成立。
若存在点x，使d（x）<2n-1，令A={a|a与x相邻}，B={b|b与x不相邻}，则由d（x）<2n-1知，B非空，取b∈B（图1）。
由题意，|A|≥n，所以1≤|B|≤n-1。
由于d（b）≥n，而b在B中的度不大于n-2，所以b必与A中的两个点p、q相邻，得到C4。
综上所述，命题获证。
再考虑采用“中间点扩充”的方法：先找2个点x、y，使x、y出发的角对接，即与x、y相邻的点集合D（x）、D（y）有2个公共点，即证明| D（x）∩D（y）|≥2（图2）。
实际上，任取点x、y，因为d（x）≥n，d（y）≥n，所以d（x） d（y）≥2n，但无法证得| D（x）∩D（y）|≥2，是因为x可能属于D（y）。
为了使x不属于D（y），可假定x、y不相邻（否则为K2n，结论显然成立），这样，x、y所引出的2n条边都是与其余2n-2个点连的边，而2n=（2n-2） 2，由抽屉原理，x、y必有2个公共的邻点（即| D（x）∩D（y）|≥2）。
【新写2】若任何两个点都相邻，则G为K2n，结论显然成立。
若存在两个点x、y不相邻，依题意，| D（x）|≥n，| D（y）|≥n，
但| D（x）∪D（y）|≤2n-2（总数2n去掉x、y），所以| D（x）∩D（y）|≥2，取u、v∈D（x）∩D（y），与x、y构成C4。
【新写3】（解答原题）我们计算“2-链”的总数S。
对任意一个点x，因为d（x）≥n，以x为中心的2-链条数不少于Cn²，所以S≥2nCn²=n²（n-1）。
因为2n个点组成的2点对个数T=C2n²=n（2n-1），所以
S-T≥n²（n-1）- n（2n-1）= n（n²-3n 1）。
对每两个点，取定一条连接它们的2-链（如果有的话），这样至多取定了T条链，至少还剩下n（n²-3n 1）条链，每条剩下的链都与一条前述取定的链组成一个C4，得到n（n²-3n 1）个C4，命题获证。
遗留问题：已知n阶简单图G中存在长为4的圈C4，求其最小度的最小值；
已知n阶简单图G中存在长为5的圈C5，求其最小度的最小值。
【题感】从条件看，只涉及边“总数”信息，没有各顶点“度”的信息，只能采用计算“2-链”总数，由两条“2-链”拼合的方法。
为计算“2-链”总数，需要从每条链“中心”的度入手，所以需要引出容量参数：设出每个顶点的度。
【题感】由条件看，只涉及边“总数”信息，没有各顶点“度”的信息，只能由“边”扩充为三角形。上题类似，需要引入容量参数：设出每个顶点的度。解法也与上题相近。
【容量参数】记顶点i的邻域为D（i），度为di ，则条件变为Σi=1ndi=2m。
【由“边”扩充】对G中的任何一条边（i，j），
| D（i）| | D（j）|= di dj，| D（i）∪ D（j）|=n，
所以，| D（i）∩ D（j）|=di dj -n。
因为D（i）∩ D（j）中的每个点都与边（i，j）组成三角形，由而含边（i，j）的三角形有di dj -n个。
【注】为方便复制编辑，特提供纯文本文档如下：
本文中所指的r-圈是由r条互异的边构成的一个圈，记为Cr。
众所周知，图论中涉及圈的定理通常只指存在某种圈，但并不能确定圈的具体长度。若要找r-圈，则可采用以下扩充策略。为叙述问题方便，我们先给出如下的
定义：两条有公共顶点的边组成的图称为“2-链”，公共顶点称为2-链的中心，另两个顶点称为2-链的端点。类似定义t-链。
一般地说，寻找图G中的r-圈，有以下4种常用策略。
（1）由一条“2-链”扩充：取2-链ABC，然后由两端点A、C向两边扩展成更长的链，最后在两端点的邻域中找公共点，或邻域中各取一个点相连。
（2）由一条边扩充：取边AB，然后由两端点A、B向两边扩展成更长的链，最后在两端点的邻域中找公共点，或邻域中各取一个点相连。
（3）由中间点扩充：取两个中间点A、B，在边AB（可能是虚边）两侧分别扩充。
（4）由两条t-链拼合：令每条t-链与其两个端点对应，证明有2条t-链对应同一个“2点组”，则这2条t-链拼合成一个长为2t的圈。
值得指出的是，当r不同时，找r-圈的技巧又略有不同，我们以典型的圈C3、C4为例。
找三角形仅有2种常用策略：
（i）由一条“2-链”扩充：取点A为“2-链”中心，证明A的邻域中有2点相邻（通常用到“邻域分块”、“充分条件分类”等技巧）；
（ii）由一条边扩充：适当取边AB，证明两端点A、B的邻域有公共点，即
|D（A）∩D（B）|≥1。
找四边形有4种策略：
（i）由一条“2-链”扩充：取点A为“2-链”中心，证明有一个异于A的点向A的邻域引出两条边（与邻域中两个点相邻）；
（ii）由一条边扩充：取边AB，证明A邻域中一点与B邻域中一点相邻；
（iii）由点对扩充：取两点A、B，证明A、B的邻域有2个公共点，即
|D（A）∩D（B）|≥2；
（4）由两条2-链拼合：令每条2-链与其两个端点对应，证明有两条2-链对应同一个“2点组”，则这两条2-链拼合成一个四边形。
以下用具体例子说明。
例1、若干个城市共派出2n（n≥3）名选手参加桥牌友谊赛，比赛规定：同一个城市的任何2名选手不同在同一局中作为敌我对手进行比赛。如果每个城市都至多派出n名队员，且一个队员可以比赛多次，试证：至少可以安排n（n2-3n 1）局比赛。（原创题）
【题感】由比赛规则看，同一局的4个选手中邻座属于不同的城市，于是想到用点表示选手，将属于不同城市的选手连边，得到一个2n阶简单图G。
问题变成：若每个顶点的度至少是2n-n=n，证明2n阶简单图G中存在n（n2-3n 1）个4-圈。
由目标看，为说明找圈的方法，先先退一步：假定是找“一个”4-圈的问题（见“新写1”与“新写2”），这自然可采用局部扩展策略。在此基础上，最后再解决原问题（见“新写3”）。
先考虑由一条“2-链”扩充的方法，此时需要再找一个点向“2链”中心的邻域引两条边。由此又想到邻域分块技巧。
【邻域分块】“任取”一个点x为“2链”中心，令
A={a|a与x相邻}，B={b|b与x不相邻}，
依题意|A|≥n，|B|≤n-1。
我们只需找到B中一个点b向a的邻域A引出两条边。
这有如下两个问题需要解决：
①B中有点b；②b向a的邻域A引出两条边。
对于问题①，自然想到优化假设，令最先取的点x满足：d（x）<2n-1。但这样的点x未必存在，分类讨论即可。
对于问题②，可采用反面思考：如果B中的点b至多在A中连1条边，则d（b）≤1 dB（b）≤1 （|B|-1）≤1 （n-2）<n，与条件矛盾。
【新写1】若对所有点x，有d（x）=2n-1，则G是完全图，结论显然成立。
若存在点x，使d（x）<2n-1，令A={a|a与x相邻}，B={b|b与x不相邻}，则由d（x）<2n-1知，B非空，取b∈B（图1）。
由题意，|A|≥n，所以1≤|B|≤n-1。
由于d（b）≥n，而b在B中的度不大于n-2，所以b必与A中的两个点p、q相邻，得到C4。
综上所述，命题获证。
再考虑采用“中间点扩充”的方法：先找2个点x、y，使x、y出发的角对接，即与x、y相邻的点集合D（x）、D（y）有2个公共点，即证明| D（x）∩D（y）|≥2（图2）。
实际上，任取点x、y，因为d（x）≥n，d（y）≥n，所以d（x） d（y）≥2n，但无法证得| D（x）∩D（y）|≥2，是因为x可能属于D（y）。
为了使x不属于D（y），可假定x、y不相邻（否则为K2n，结论显然成立），这样，x、y所引出的2n条边都是与其余2n-2个点连的边，而2n=（2n-2） 2，由抽屉原理，x、y必有2个公共的邻点（即| D（x）∩D（y）|≥2）。
图2
【新写2】若任何两个点都相邻，则G为K2n，结论显然成立。
若存在两个点x、y不相邻，依题意，| D（x）|≥n，| D（y）|≥n，
但| D（x）∪D（y）|≤2n-2（总数2n去掉x、y），所以| D（x）∩D（y）|≥2，取u、v∈D（x）∩D（y），与x、y构成C4。
【新写3】（解答原题）我们计算“2-链”的总数S。
对任意一个点x，因为d（x）≥n，以x为中心的2-链条数不少于Cn2，所以S≥2nCn2=n2（n-1）。
因为2n个点组成的2点对个数T=C2n2=n（2n-1），所以
S-T≥n2（n-1）- n（2n-1）= n（n2-3n 1）。
对每两个点，取定一条连接它们的2-链（如果有的话），这样至多取定了T条链，至少还剩下n（n2-3n 1）条链，每条剩下的链都与一条前述取定的链组成一个C4，得到n（n2-3n 1）个C4，命题获证。
遗留问题：已知n阶简单图G中存在长为4的圈C4，求其最小度的最小值；
已知n阶简单图G中存在长为5的圈C5，求其最小度的最小值。
例2、设n≥4，简单图G有n个顶点，m条边，如果m> ，则G中含有长为4的圈。（2000年印度数学奥林匹克试题）
【题感】从条件看，只涉及边“总数”信息，没有各顶点“度”的信息，只能采用计算“2-链”总数，由两条“2-链”拼合的方法。
为计算“2-链”总数，需要从每条链“中心”的度入手，所以需要引出容量参数：设出每个顶点的度。
【计算“2-链”总数】对每一个顶点Vi，设其度为d（Vi）=di，那么，以Vi为中心的2-链条数为 ，其中d1 d2 … dn=2m。于是，所有2-链的条数：
S= 。
【“2-链”归入点对】所有点对有 个，所以我们只需证明：
S= > 。
【充分条件（放缩法）】因为x（x-1）是凸函数，由凸函数不等式（或者展开后用Cauchy不等式）
≥f（ ），有S≥ =
只需证
实际上，上述不等式等价于4m2-2nm-n2（n-1）>0。（*）
解关于m的不等式（*），得
m> ，或m< 。
由条件，我们有m> ，由而上述不等式（*）成立。
【新写】对每一个顶点Vi，设其度为d（Vi）=di，那么，以Vi为中心的2-链条数为 ，其中d1 d2 … dn=2m。于是，所有2-链的条数：
S= 。
令每一条2-链都与它的两个端点对应，则S条2-链对应S个“端点对”。
因为x（x-1）是凸函数，由凸函数不等式 ≥f（ ），
有S≥ =
因为m> ，所以 （*）
这是因为不等式（*）等价于4m2-2nm-n2（n-1）>0。
解关于m的不等式（注意m>0），得m> 。
由（*）可知，有两条2-链对应的“端点对”相同，这两条2-链构成一个4-圈，命题获证。
例3、设G是n阶简单图，||G||=m。求证：G中至少有 个三角形。（1989年亚太地区数学奥林匹克试题）
【题感】由条件看，只涉及边“总数”信息，没有各顶点“度”的信息，只能由“边”扩充为三角形。上题类似，需要引入容量参数：设出每个顶点的度。解法也与上题相近。
【容量参数】记顶点i的邻域为D（i），度为di ，则条件变为Σi=1ndi=2m。
【由“边”扩充】对G中的任何一条边（i，j），
| D（i）| | D（j）|= di dj，| D（i）∪ D（j）|=n，
所以，| D（i）∩ D（j）|=di dj -n。
因为D（i）∩ D（j）中的每个点都与边（i，j）组成三角形，由而含边（i，j）的三角形有di dj -n个。
【通性叠合】这样，G中三角形的个数为 （di dj-n），但每个三角形有3条边，被重复计数3次，所以，G中三角形的个数：
k≥ （di dj-n）= （di dj）- n= （di dj）- mn。
【贡献算法】考察S= （di dj）中di 出现的次数：点i每连一条边（i，j），则di 在S中出现一次，注意到i连了di 条边，由而di 在S中共出现di 次（di个di相加），于是
S= （di dj）= 1= 。（即：di di … di，共有di个项）
所以，
k≥ （di dj）- mn= - mn≥ - mn= 。
【新写】记顶点i的邻域为D（i），度为di ，则 =2m。
对G中的任何一条边ij，| D（i）| | D（j）|= di dj，| D（i）∪ D（j）|=n，
所以，| D（i）∩ D（j）|=di dj -n。
因为D（i）∩ D（j）中的每个点都与边ij组成三角形，由而含边ij的三角形有di dj -n个。
G中三角形的个数为 （di dj-n），但每个三角形有3条边，被重复计数3次，所以，G中三角形的个数：
k≥ （di dj-n）= （di dj）- n= （di dj）- mn。
考察S= （di dj）中di 出现的次数：点i每连一条边ij，则di 在S中出现一次，注意到i连了di 条边，由而di 在S中共出现di 次，于是S= ，所以由Cauchy不等式，有
k≥ - mn≥ - mn= 。
综上所述，命题获证。
,
