一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
想学计算机系却报错志愿进了数学系，该怎么办？是什么让你对数学或物理感兴趣的？
数学中那些充满构造性的证明是怎样想到的，有没有可以遵循的一般性的数学思想方法？
是什么让你对数学或物理感兴趣的？
有哪些千年以上时间才解决的数学问题?
泊松分布和正态分布有什么内在联系？
任给N个连续的整数，是否能从中找到一些数（至少一个），使得它们加起来是N(N+1)/2的倍数？
Diffie-Hellman密码交换是如何运作的？
如何解决这个数学问题?
小偷能逃出无数个警察的包围圈吗？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
一道初等数论作业题，请问怎么解决？数学专业考研（数分高代）如何做笔记？
为什么 3 岁小朋友也能一眼识别三叶草和四叶草，是根据形状还是根据叶子数量判断的呢？
什么是埃尔德什差异问题?
如何理解有限单群分类定理？
如何看待这位知友提出的这个声称只有他能解的问题？
高中数学教材中，规定0向量与任意向量平行。为什么要做这样的规定？有什么意义和必要性？
为什么要用文字定义多项式，而不是直接将多项式函数定义为多项式？
怎么看待搞民科的人?
这张图中能数出多少个三角形？
如何计算这个积分？
是否存在这样一个初等函数：它的三阶导数是其本身，而一、二阶导数不是其本身？
如何优雅地测量一只猫的体积，而不使其感到惊恐或受到伤害？
牛顿莱布尼兹公式指出求导和积分互为逆运算。从几何的角度看求斜率和求面积似乎并没有直接联系？
如何看待 Atiyah 宣布证明了黎曼猜想？
你知道哪些与数学有关的小故事？
数学系大一学生学习数分时看一页书花 20~30 分钟合理吗？
有哪些有趣的概率问题？
十个人赛跑第一名和一百人赛跑的第十名，谁厉害？
一个有n条边的简单图最多有几个三角形?
10 × 10 的正方形最多可放入多少个直径为 1 的圆？
芝诺佯谬的正确解释是什么？
成功概率为 1% 的事件，理论上平均要尝试到第几次才能成功？
为什么法语的数字表达方式那么奇怪？世界上还有其它主要语种采取类似的数字逻辑吗？
有理数的开方，是否能取遍实数？ 换句话说，是否存在无理数，不是某有理数的开方？
俄罗斯数学近况如何？
如何证明对于任意大于 1 的正整数 n，(1＋√2＋√3＋…＋√n) 均为无理数？
请问这到微积分证明题题怎么证?？
请问这题积分怎么求?
如何利用群论的知识解决三阶魔方？