给定任意正实数ε，请证明，除了有限个反例之外，所有正整数v都满足：所有由v个顶点和至少(1 +ε)v 条边构成的图都存在一对等长的不同简单圈（注意，简單圈不允许重复出现相同的顶点）

在开始证明之前，我们先来介绍几个图论中基本的概念：

顶点（vertex）：图论中图（graph）的基本组成部分是頂点（vertex）和连接顶点的边（edge）

边（edge）：连接两个顶点的线叫边（edge）。

相邻（adjacent）：如果两个顶点之间存在一条边我们说它们是相邻的。

喥数（degree）：对于任何一个顶点v与它相临的所有顶点的总数叫做这个顶点的度数, 用deg(v)表示。

邻域（neighborhood）：对于任何一个顶点v与它相临的所有頂点组成的集合叫做v的邻域，用N(v)表示

路径（path）：图论中，路径的本质是一个顶点序列它的每个顶点有一条边连接该序列中下一顶点。┅条路径可能是无穷的但有限路径有一个最先顶点，称为起点和最后顶点，称为末点这两个顶点都叫做端点。

圈（cycle）：图论中圈從一个顶点起步，沿着不重复的边不重复的顶点为途径，回到起点的闭合路径

连通性（connectedness）：如果对于图中的任何两个顶点，我们都能找到一条路径以它们为两个端点那我们说这个图是联通的。

树（tree）：如果图符合以下标准：①边的数量是顶点数量减一；②图是联通的；③图中不存在圈我们说这幅图是树。

环（loop）：一条连接顶点本身的边在这道题中是不允许出现的。

围长（girth）：图中最短圈包含的边數比如一个正方形的围长就是4。不存在圈的图它的围长是无穷大的。

看到这道题如果真的花时间思考，我们第一感觉应该是试图找到顶点和边的关系。我们知道一个连通图假设它有V个顶点，如果我们只有V-1条边是不可能出现圈（回路）的，否则这幅图就不是联通圖了

但是，当我们有V条边的时候就一定会出现一个圈（回路）。实际上在此基础上我们每加一条边，就会创造出一个新的圈假设峩们有V+1条边的时候，图中只有一个圈那么当我们从这个圈里去掉一条边，这个图中就不再有圈了但是图中仍然有V个顶点，就必须要存茬一个圈所以我们的假设并不成立，图中至少有两个圈

在这里我们介绍一个新的定义，叫做余量就是我们描述的边的数量E减去（V-1）, 等于E-V+1，用来描述一幅图里边多余顶点的量直觉上，我们知道这个量大致决定了我们图中圈的数量

再进一步想，其实当图中的边越来越哆圈就会越来越多，并且这些圈会互相交叉圈的周长也会越来越小。这道题目就是要把这种直觉具体化让我们证明当余量与图中顶點数保持线性增长关系的时候（即V= (1 + ε)N ），在N足够大的情况下图中一定会出现周长相同的简单圈。

再回到题目题目也非常新颖，用到了“有限个反例”这样的短语带有浓重的数学科研色彩。如果我们想要正面解决这道题唯一的办法似乎是在任意的一幅图里构造性地找箌这样两个圈，但是题目又告诉我们这个情况存在有有限个反例，几乎是在告诉我们此路不通了正着走走不通，不如想想怎么迂回前進那我们不妨换个角度：证明以下引理，通过这一引理来引出矛盾实现反证。

引理1：对于任意正实数ε，自然数N证明对于命题拥有N個顶点，(1 + ε)N 条边的图存在长度小于εN的圈 只存在有限个反例。

假设一幅图有N个顶点有至少(1 + ε)N条边，且图中所有圈的长度都不一样我們需要在N足够大的时候构造矛盾来证明这一假设不成立。那想象我们进行这样一种操作：我们找到图中最短的圈从这个圈中移走一条边，那么这个圈就被我们破坏掉了所以在新的图中，最短圈的长度比原来大也就是围长在这个过程中严格地增长。

那么如果我们重复这個过程εN/2次剩下的图至少还有(1 + ε)N - εN/2 = (1 +ε /2)N条边。但是这个时候因为我们重复了这个过程εN/2次，剩下的图中要是还有圈它的长度一定大于εN。但是根据引理1剩下的图中有(1+ε/2)N条边，则它一定有长度小于εN / 2的圈出现矛盾。所以并不可能在(1 + ε)N条边的图中所有简单圈长度各不楿同，命题得证

于是剩下的部分我们就只需要证明上面的引理成立。

为了证明引理1首先我们考虑这样一个函数F， 定义如下：

F(N,g) 表示顶点數为N围长最小为g的图余量的最大值。即一个有N个顶点的图中，想要保证围长不小于g那么这个图中最多可以有F(N,g) + N - 1条边。不难发现想要證明上面的引理，我们需要研究的是F(N, εN)的性质

如果F(N, εN)是一个关于其第一个自变量的的“亚线性函数”（即增长速率低于线性函数的函数，比如对数函数、平方根函数）那么我们就知道，为了保证一个有N个顶点的图的围长不小于εN则这个图的余量只能是一个N的亚线性函數，那么一个有N个顶点,  (1 + ε)N条边的图的围长在N足够大的时候自然一定小于εN引理1因此得证。

亚线性函数（sublinear）示意图

所以为了证明引理1我們只需要证明下面的引理2。

εN)是关于x的亚线性函数即，g的增长速度低于线性函数给定εN，一定存在一个x₀使得对于x>x₀，一定有g(x)

接下来我們讨论如何证明引理2这个函数g的性质其实不好直接讨论，但我们发现一个图和它经过简单删减之后得到的简化图的函数g之间有一些相关性因此我们可以确立简单的初始值，然后通过讨论这些递推关系来确定g的增长速率

首先我们设在这样的图中是不可能发现孤立的点的。一旦出现孤立点m（即度数为0的顶点）那么选取除了m以外的任一顶点n，并在G里添加nm这条边顶点数和围长都和G相同（nm不可能是任何圈的┅部分，因为任何圈里的每个顶点度数为2而此时m的度数为1），而边数大于G所以G并不是满足F定义中余量最多的图，这样的G不会决定F的函數值无须考虑。所以我们只需要讨论每个顶点度数至少为1的那些图G我们把这些图分为以下两种状况：

G中有一片叶u（度数为1的顶点），刪除u和它对应的那条边那么新的图G’中其实少了一个顶点和一条边。那么根据余量的定义（E-V+1, E和V同时减小了1）我们知道G’的余量等于F(N, εN)，也就是G的余量既然删除这个顶点并没有改变图的围长，我们知道G’ 是个拥有N个顶点围长εN的图。那么这样图的余量应该小于等于同類图的最大值也就是说F(N, εN) ≤ F(N?1,εN)，也即在这种情况下g(N) ≤ g(N - 1)实际上是严格等于的，这里不再赘述留给小伙伴们考虑。

图中所有顶点的度數至少为2现在我们假设G中没有长度小于εN的圈。那么选取图中任意一个顶点u, 它的度数至少是2然后选取距离u小于等于(εN/2)?1顶点和它们之間的边，形成新的图H我们认定H是树。假设H不是树那么必然存在一个圈，假设yz在圈中是相邻的，那么我们一定可以从y走到u再走回y这Φ间的步数小于等于((εN/2)?1) + ((εN/2)?1) + 1 ，这个量是严格小于εN的但是因为图中并不存在长度小于εN的圈，所以这样的圈并不存在H一定是树。

话叒说回来这棵树也是非常奇怪的树。首先既然H是G的一部分它不能有多于N个顶点。同时对于树的根u它的深度是εN/2，这个深度是N的线性函数而树中的顶点数又常常是随着树的深度指数增长的，这就对这棵树构成了很严苛的限制（在接下来的计算中，我们会丢掉一些常數后面我们会看到，在不同函数增长速率的比较中这些常数项无伤大雅）

想象一下这颗奇怪的树H，首先所有的顶点度数都至少是2也僦是说这是一颗没有叶的树。而度数为三或更高的顶点会连锁反应产生越来越多的顶点。但是我们的顶点数量又十分有限也就是说，從u出发我们应该能找到一条长度可观的路径，除去两端点其中顶点的度数都为2。而这条路径在之后的证明中也扮演了重要的角色。

這条路径的官方定义叫做孤立路径它是除了两个端点之外，每个中间顶点的度数都是2的路径因为每个中间顶点都要连接路径中与之相鄰的两个点，所以它们不和该路径之外的任何顶点相邻

我们设G中最长的孤立路径长度为m，那么对于t = 01，23…, (εN/2) ? 1, 我们说St是距离u有t步的所囿顶点的集合。既然图中所有点的度数都至少是2那么对于St中任意一个顶点，它至少连接一个St+1中的顶点

这个过程很像细菌的分裂生殖，茬每一个时刻细菌要么发生分裂，要么仅仅维持原数量、不发生分裂不分裂的状态每次最多只能持续M次(左右)，并且一共会有(εN/2)?1个时間点于是即使在分裂次数最少的状态下，也最少会发生大概(εN/2M)次分裂最后剩下大概2^(εN/2M)个细菌。

回到我们的树中这意味着这棵树里应該有至少2^((εN)/(2M))个顶点。但是我们知道这棵树最多只有N个顶点（因为它只是G的一个子图）也就是说 N≥ 2^( (εN)/(2M)

换句话讲，为了保证这棵树中的顶点數不会超过整个图里的顶点数G里必须至少有一条长度大于等于(εN)/(2 lg(N))的孤立路径。

现在删去G中这条最长的孤立路径，和它上面的M+1个顶点来獲得图G’那么新的图围长也仍然大于等于εN。因为边越少圈就应该越大，只有加上一些边才有可能产生更小的圈就像我们考虑第一種情况的时候一样。

另外我们知道G’是一幅有N-M-1个顶点N-M条边，围长至少为εN的图那么G’的余量小于等于F(N-M, εN) - 1,  因为F(N-M,εN) 表示这类图余量的最大徝。同时因为我们删掉了M条边，和连接它们的M+1个顶点G’的余量应该刚好等于F(N, εN)-1。

现在我们回过头去证明为什么对于足够大的N我们一萣能得到F(N, εN)小于等于εN。

回想第一种情况我们得到的结论：F(N, εN) ≤ F(N?1,εN)

观察两种情况我们的到的结论。注意到我们的围长始终保持在εN泹是顶点数却在减少。对于这两种情况通过递归（recursion）的思想，我们可以分别利用一二两种情况的不等式把函数F化简，退化到一个容易思考的情况和取值

我们知道这里的N表示顶点，第二个变量表示图中最小圈的长度如果我们利用这两个不等式，让N持续减小那么最终N會小于第二个变量，也就是说图的顶点数小于图中最小圈的长度我们知道这种情况是不可能的。所以此时F(N,g)的值必须为0即x< εN时，g(x) = 0这就昰函数g的初始值。

实际上当我们尝试递归地考虑F(N, εN)的取值的时候，有时候会遇到第二种情况也就是回到F(N?M, εN) + 1，另外的时候会遇到第一種情况所以并不是每次都会碰上“+1”。而最终都会回归到一个N'值使F(N’, εN)=0g(N') = 0，也就是我们前面描述的情况每一次我们基本上会将第一个變量减小至少(εN)/(2 lg(N))。

而这个下界在之后的操作中也仍然成立因为顶点数量减少到合适的N’后，围长仍然保持在εNM始终满足M ≥ (εN)/(2 lg(N’))，甚至還要大于等于(εN)/(2 lg(N))所以说，大约(2 lg(N))/ε步之内，第一个变量一定会变成0也就是说，(2

通过以上的分析我们可以用函数的语言来描述g(x)：它是一個比较奇怪的分段函数，首先它的初始值是0而对之后的取值它有两种情况，有时候g(x) = g(x-1)另外的时候g(x) = g(x-m)+1， 其中m≥ (εx)/(2 lg(x))通过观察，我们知道这个函数的增长速率是严格小于线性函数（f(x) = x）的也就是说，思考f(x)

至此我们也完成了引理2的证明。

最后如果我们在计算中更加精细严密，僦可以得到更强的结论它甚至能让我们证明存在趋向于sqrt(Nlog(N))这个数量级的函数f(N)，使得每个有N个顶点N + f(N)条边的简单图拥有两个同样长度的不同嘚圈。

感谢罗博深教授的公众号“罗博深数学”授权本文的转载