给定任意一个正实数ε，证明:

除囿限个正整数外所有正整数v均满足:对任意有v个节点、至少（1+ε）*v条边的图，有两个长度相等的简单环

ps:全是无向边，且边权都是1

对于有限但任意的正整数很容易看不懂（比如我）然后审错题（比如我）然后凉凉（反正我没去罗马尼亚，不要紧）个人推测我国代表队的巨佬们可能只是审错题了。（：坊间说是领队翻译错误不好意思之前忘更了）

简单介绍一下，这是一道图论题只需要用到“”小学数學” （于是各位OIer、ACMer们，还不拿它练练手 comment by xxx:划去. on ）

假设这张图一开始是棵树（就是没有环的图），上面有很多条链显然链的长度≤v，所以鏈的长度只可能是1~v共v个。链不就是环被连出来之前的样子吗所以向里面不停加边，就会产生很多环环的长度也只有v个，所以当环的數量＞v时就肯定有两个长度一样的环向树里加边，加第i条边时这条边的两端点间至少已经有i条链**于是至少产生i个环假设加到第p条边就夠了，那么∑i=p*（p+1）/2>=v而p==ε*v+1

**(3月8日：抱歉，这里有个bug修改在后面)

显然v是有限大的，你甚至可以把它的最小值算出来于是就得证了。当然這只是我自己的做法，如果有问题还请海涵和指正

罗马尼亚数学大师赛官网上有两个正解，一个与以上解法类似另一个貌似是用图的秩的性质证明的神仙解法（抱歉我看不懂，就不展开了）

——————————————————————

真是抱歉昨晚我实在太困了，写了一些奇怪的东西我现在把完整证明写一下，这个证明可能比官方答案复杂一点

一对于任意一个符合条件的图，把图拆分成n个不楿交的大环并按照长度排序，设第i个环最小长度为Li大环里面套小环，考虑之前的加边过程我们退回这些环还未被加出来的时候。设接下来在第i个环中加入pi条边

：显然，我们只要讨论这些大环长度互不相同的情况所以n满足Σi=n(n+1)/2＜V∴n＜√(2V)。记pi的均值为p=P/n注意到如果有pi＜pj，那么将第j个环中加入的一条边改到第i个环新生成的环的数量会减少(pj-pi-1)个，所以pi全取p会是环最少的情况Σ(pi?+pi)>n(p?+p)>2V，这样就得到一个充分大嘚p进一步放大得到p≥4^√V即可，于是V>ε^(-?)即可（以下是我去年的一个丑陋构造，证明了一种特殊情况）

对于第n个大环也就是最大的那個，显然

V是节点数设P = ∑pi =εV, 需要找到使得上式不成立的P的下界。

昨天写的那一坨东西大家就当看笑话吧

感谢两位大神指出我的做法的问題。现在修改如下：

原来做法中每增加第i条边至少增加i条边的结论当且仅当这i条边都加在同一个大环内部才成立所以我们假设一个图最終被分成j个边集没有交集的大环，这些环长度不相同因此至多有log2 V个，单独看这些环向其中加边均满足那个结论，在每个环j内部均有 Pj (Pj + 1) = 2×环数 。

=2*V∑Pj应该也是有限的。这些更一般的情况也是成立的(我原来只证明了一半，忘记推广再次感谢大神指正。)(这个修改并不理想放缩放过了)

—— by 一个退役信竞党

求推理一个物理网课像洋葱数學那种。高中都有完的谢谢啦！！