一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
如何评价组合数学（combinatorics）这个学科？“黎曼猜想在公元2030年之前（含2030年）被证明的概率大于等于60%”这个陈述是不是命题？
为什么手机计算器上50%+50%=0.75?
如何评价望月新一？
“太阳从西边或东边出来”是必然事件，随机事件还是不可能事件？
为什么数学中一定要强调加法交换律？
有什么与数学名词有关的趣事?
这题怎么写？急！?
我好喜欢数学，学不好，怎么办？
有什么数学定理一般人都觉得是常识，但严谨证明起来却挺费力的？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
如何看待哈工大校友刘汉清如今靠400元低保度日？北京国际数学研究中心教授谢俊逸和袁新意解决几何 Bogomolov 猜想难题，如何理解这一工作？
5×3還是3×5？
4x5的表写入20个不同正整数，相邻数不互质，表中最大的数至少是多少？
数学中的错误有大错和小错的区别吗？
你所在的科研领域有哪些做不动的问题？
有哪些手算对数的方法？
数学对于编程有多重要？
怎么评价北大版的《高等代数》？
数学建模入门请问要学习什么?
一天做完一百道积分题是一种什么感觉？
圆周率已被算到31.4万亿位，科学家如此执着，到底为了什么？
如何看待π这个无理数？
如何笔算解码二维码？
9.99循环这个数存不存在，如果存在，那么它是整数还是无限循环小数？
如何用数学方法计算灯泡的体积？
在 UCLA 陶哲轩手下读博是什么感受？
这个题怎么求概率？
高等数学和生物技术有什么关系？
两端固定的纸张拱起所成曲线的方程是什么？
「计算」会改变信息量么？
什么是上极限？
如何用初等数学证明2的a次方（a大于零）大于1？
如何通俗理解常微分方程，解对初值的连续依赖性？
有没有在高考数学中使用洛必达法则而不扣分的方法？
逐渐丢失对数学的兴趣，怎么办？
如何证明哈代不等式?
如何看待喜欢玩数独却连微积分都不会的人？
数学中以 e 为底的指数函数 f(x)=exp(x) 求导后为什么还是它本身？
假如我在高考数学试卷上解决了哥德巴赫猜想会发生什么？