垫脚石（此题 → 相关题） 2012 年安徽预赛 第 12 题 · P010331
先用比赛图练习“每条边两端度数和”与柯西不等式的边数界，再把这个引理放进负点积向量对形成的图。后一题先靠平面几何排除四点完全图，再对最大度顶点的邻点集使用无三角形引理。
前题全图直接无三角形，并可用两组之间比赛达到界；后题只保证最大度顶点的邻点集无三角形，还须拆分其余边集并优化度数。
培玉 · 一试
2025 年江苏预赛
F4解答题组合计数综合
有 支队伍进行单循环赛（任意两队之间至多进行一场比赛）。在比赛了一个阶段后统计， 发现任意 支队伍之间至多进行了两场比赛。求此时这 支队伍之间比赛总场次的最大值，并说明理由。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
度数是某队已赛过的不同对手数。握手定理指总度数等于边数的两倍。Mantel 上界是无三角形简单图边数不超过顶点数平方的四分之一，这里用度数双计数直接证明，无须预先引用定理。
想法从哪来：“任意三队至多两场”说明不存在三队已经互相都赛过，所以先把比赛安排看成一个没有三角形的简单图。若要构造很多场，试把队伍分成两组，只赛跨组，天然避免三角形；两组人数越平衡，乘积越大，由此得到一个候选上界。 证明不能更大时，从任意一场比赛两端出发：两队不能有已经共同交手的第三队，否则形成禁三角形。因此两端度数之和不超过总队数。对所有已赛边累加，每个队的度数会被重复其度数次，得到度数平方和上界；另一方面，总度数由比赛数确定，柯西给下界。两界合用便把场次数锁住，最后与构造对照。
把队伍视为顶点、已经比赛视为边，条件等价于所得图不含三角形，应用并证明 Mantel 上界。
解答
设比赛图有 个顶点、 条边，顶点 的度数为 。图中不含三角形， 所以对任一边 ， 没有公共邻点，从而
对所有边求和，得到
另一方面，由 Cauchy 不等式和握手定理，
若 ，合并即得 ，故 。 把 支队伍分为 支与 支两组，只安排不同组之间的比赛，共有 场；任意三队中必有两队同组，故至多有两场比赛。所以上界可达，最大值为 。
复核
完全二部图 确有 条边且无三角形；上界证明覆盖所有简单比赛图。
方法总结
“任意三点至多两条边”正是禁三角形条件。可用每条边两端度数和不超过顶点数，配合 Cauchy 不等式得到 Mantel 上界，并用平衡完全二部图构造等号。
为什么评为 F4（会透露解法方向）
须从无三角形推出每条边两端度数和的界，双计数结合平方和下界，再构造4与5分组达到上界。
联系 · 1 条
已记下，谢谢！