一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
为什么欧几里得在《几何原本》中的第四公设要设定所有的直角都相等？有哪些形式简单却很难证明的不等式？
小时候想到的一个数学问题，现在还没有想明白，可能以后会越来越不明白，有哪位大牛可以帮我解答吗？
如何比较 √2与log3（5）的大小？
什么是埃尔德什差异问题?
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
确定不做学术，应不应该读纯数学的博士？
编程是否存在终极问题？
σ-代数为什么叫代数？它有代数结构吗？
与1相邻的实数存在吗？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
10 × 10 的正方形最多可放入多少个直径为 1 的圆？你所见过的被引用次数最多的文献是哪本？
求问数学公式推导？
如何理解出租车几何学？
求解一道关于级数的问题怎么证明？
有没有这样的函数，其一阶导等于1，二阶导等于2，三阶导等于3，n阶导等于n，n一直趋于无穷大？
数学中有哪些让你感到赏心悦目或是震惊的构造手法？
康托尔著名的对角线证明？
无穷等于无穷吗？
柯西审敛原理是证得收敛还是一致收敛?
家境普通的姑娘想学物理或数学，怎么看？
皮克定理有哪些证明？
等比数列的任意连续三项的中间一项都是另外两项的等比中项吗？
我本科是信息与计算科学专业，想考研但是不知道选什么专业，在纠结考数学还是计算机？
985工科毕业生想跨考基础数学，是理性伟大还是自负骄傲（中二病）？
除了 1 和 144，还有哪个斐波那契数是平方数?
这个结论是对的吗？能否初等证明？
如何评价 2021 年各卷高考数学题？有哪些「出其不意」的题和解法？
数学老师遇到很笨，对数学毫无天赋的学生，心里的真实想法是什么？
如何看待京都大学的望月新一教授证明「ABC 猜想」，发表在其主编的期刊上？
什么情况下被积函数的原函数不能用初等函数表示？怎么判断呢？
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？
如何证明树的树叶个数比度数不少于3的顶点数多？
哪些看似与图论无关的问题可用图论模型解决？
我有一篇关于0可以作除数的文章，请教如何分享给他人？
为什么大多数物理公式中乘法和乘方相比加法来说占了多数？
遇到数理化难题容易头晕是智商低吗？？？
一道数学分析题? 应该如何做呢?
7 x 8 + 14 x 18 + 42 × 13 的简便运算方法？
数学上，「数」是怎么定义的？