一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
多项式由系数唯一决定，在中学或大学数学课上证明过吗？对大多数人来说数学无用，但要高考，不想学数学，怎么克服这种心理？
线性代数有什么用？学习线性代数的意义在哪？
数学中，有哪些方程和思想让你体会到了美感？
平分三角形面积的所有直线的所有交点是什么图形？
0.8＞ln2 怎么证明？
是否区间 [0, 1] 内的代数数都可以表示为 sin²(kπ)（其中 k∈Q）的形式？
矩阵乘法的本质是什么？
有没有一个函数求导后幂会变高？
刚看了一个柯西不等式的推论，不知如何证明，希望得到解答?
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
关口知宏的《中国铁道大纪行》里面的路线设计本质上是不是就是图论里面的“最长路径问题”？为什么世界上大多数地方的人习惯用逗号表示小数点，而C++却用圆点表示小数点，而不是按照大多数地方习惯？
这个极限正确答案应该是e的1/3次方，这样计算的结果却是e的-1/3次方，请问有什么问题吗?
10 × 10 的正方形最多可放入多少个直径为 1 的圆？
普通外国人算术真的很差吗？
下面这个关于质数的不等式如何证明？
欧拉到底有多厉害？
100 万和 50% 的机会拿到 1 亿，你会选哪个？
如果 1+1 等于 3，其他不变，比如 1+2 还是等于 3，那世界会是什么样的？
理想情況下，对于任意一种台球布局，是否存在一个击球方案，一杆就能使所有球进洞？
有关大学物理推导的微分运算是否合理？
数学仅仅是人类创造的工具吗？
你相信数学吗？
为什么数学中“有且仅有”不可以说成“仅有”？
数学史上你认为最美的公式是什么？
有没有大神回答一下，级数中，比值判别法中的ρ是指什么？
那些数学很好的人现在怎么样了？
高中数学教材中，规定0向量与任意向量平行。为什么要做这样的规定？有什么意义和必要性？
怎么比较 33 的 11 次方与 17 的 14 次方的大小关系？
这个一元三次方程可以得到以下式子吗，属于因式分解吗？
(lnx)'＝1/x，为什么 (ln3)'≠1/3？
如何推导以下几种连分数表示？
为什么感觉群论学起来比数学分析之类难好多？
请问该如何证明？
为什么经济学专业要学拓扑学？
为什么数学期刊的 IF 普遍不高?
世界是个方程吗？
如果 f(x) 与 g(x) 均为周期函数，判断其相加后的周期性？
如何考虑这个2022贺年题？
超理论坛是个怎样的论坛？