对于任意给定的正数 $\varepsilon$，试证明对于全部有限的正整数v，任意含有v个顶点并含有至少 $(1+\varepsilon)v$ 条边有两个等长的简单圈。
【难度】
【出处】
2019第十一届罗马尼亚大师赛
【标注】
【答案】
略
【解析】
固定一个正实数 $\varepsilon$，设 $G$ 是一个有 $v$ 个顶点的图，并且有至少 $(1+\varepsilon)v$ 条边。所有的简单圈都具有不同的对偶长度。
假设 $\varepsilon^{2}v\geqslant 1$，我们来针对 $G$ 中的简单图的个数来寻找一个和 $v$ 线性相关的上界和 $v^2$ 线性相关的下确界。
因为G中的简单图最多含有v个顶点，每个长度最多含有其中一种，所有G中至多含有v个不同的对偶简单圈。这就建立了我们想要的上界。
对于下界，我们针对G图中的各个元素来考虑他们的生成树。组合起来形成一个生成树林F。设集合A包括F中的所有边，集合B为G图中剩下的边。显然我们可以得到 $\arrowvert A \arrowvert \leqslant v-1$，所以 $\arrowvert B \arrowvert \geqslant (1+\varepsilon)v-\arrowvert A \arrowvert \geqslant (1+\varepsilon)v-(v-1)=\varepsilon v +1>\varepsilon v$ 。
对于B中的任意一条边b来说，和F组合即可得到一个特别的经过b的简单圈 $C_b$，设 $S_b$ 为A中经过Cb的集合。$$\sum \arrowvert S_{b} \arrowvert> \arrowvert B \arrowvert^{2} /2 > \varepsilon^{2}v^{2}/2$$得到了我们想要的下界。
假设 $\varepsilon^{2}v\geqslant 1$，我们来针对 $G$ 中的简单图的个数来寻找一个和 $v$ 线性相关的上界和 $v^2$ 线性相关的下确界。
因为G中的简单图最多含有v个顶点，每个长度最多含有其中一种，所有G中至多含有v个不同的对偶简单圈。这就建立了我们想要的上界。
对于下界，我们针对G图中的各个元素来考虑他们的生成树。组合起来形成一个生成树林F。设集合A包括F中的所有边，集合B为G图中剩下的边。显然我们可以得到 $\arrowvert A \arrowvert \leqslant v-1$，所以 $\arrowvert B \arrowvert \geqslant (1+\varepsilon)v-\arrowvert A \arrowvert \geqslant (1+\varepsilon)v-(v-1)=\varepsilon v +1>\varepsilon v$ 。
对于B中的任意一条边b来说，和F组合即可得到一个特别的经过b的简单圈 $C_b$，设 $S_b$ 为A中经过Cb的集合。$$\sum \arrowvert S_{b} \arrowvert> \arrowvert B \arrowvert^{2} /2 > \varepsilon^{2}v^{2}/2$$得到了我们想要的下界。
答案
解析
备注
