一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
如何看待部分明显不具备相关领域基础知识的公众号和用户在各种专业问题下强行「科普」的现象？奶茶咖啡等饮料全换成纸吸管到底能降低多少污染？
两块完全一样饼，如何平均分给三个人？
为什么我们可以用平面取一点来证明概率为零事件能发生？
如何看待知乎用户李归农嘲讽数学家华罗庚被驳斥无回应？
证明定理创造新的信息吗？
甲有101个硬币，乙有100个硬币，两人随机撒在地面上，甲比乙正面朝上多的概率是多少？
数学理论上可不可以绝对识别ps过的照片（可以作为法律证据的）？
既然牛顿的导数理论是有问题的，为什么现在高中依然在教牛顿的导数理论而不是威尔斯特拉斯的 ε-δ 语言？
喜欢数学但没有天赋能不能做研究？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
为什么国内一流高校的理工科专业的学生大多对民科充满反感和鄙夷？同时满足两个不同等差数列的数是否组成等差数列？如何证明？等比数列呢？
如何证明 π > 3.05 ？
n的正因子个数d(n)有没有上界公式？
做科研时，简化了领域内一个大佬的证明值得发表吗?
你见过什么复杂到让你目瞪口呆的公式？
如何看待郑爽小号疑似曝光：按前男友顺序编号注册微博小号，每个小号数字还是以 4 递增的等差数列？
对人类推动最大的学科是物理还是数学？
S²×S¹是否可以嵌入到R⁴中？
正常的生活是否会限制数学家的发展？
为什么「正态分布」在自然界中如此常见？
这道题怎么做?不懂？
想读数学系，南开大学、同济大学和南京大学哪所比较好？
本科数学系，未来只在业余时间做数学研究有可能吗？
请问这个如何做？
请问这个关于全排列的图论结论如何证明？
这个积分问题怎么做？
我好喜欢数学，学不好，怎么办？
如何证明这个由Abel定理得到的结论？
这个问题怎么做?最后怎么解出多项式？
两块完全一样饼，如何平均分给三个人？
如何用初等数论知识证明26是唯一夹在一个平方数和立方数间的正整数？
中国最难的理科高考题有哪些？
为什么正态分布公式中会有 π 呢？ π 为什么应用得地方那么多，应该怎么理解 π ？
柯洁与 AlphaGo 三场皆负，对围棋今后的发展会有哪些影响？
Ln(-3-3i)等于多少？
数学符号是不是在一定程度上阻碍了数学的发展？
这道数列极限题怎么解 涉及到排列组合 不会啊?
两个有理数之间一定存在一个无理数吗？
为什么美国中小学生学的数学比我们简单，美国人却还能做出超级牛的东西？