一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
如何估计这个级数？在上学的同时自学完这些物理、数学、计算机技术、哲学等内容，大概需要多长时间？
X²+Y²+Z²=114514存在多少组整数解？
除了 1 和 144，还有哪个斐波那契数是平方数?
如何看待某人口专家言论「中国人口根本不可能塌陷式下滑，甚至雪崩」？
知乎现在都有哪些值得关注的严肃输出？
《现代数学基础丛书》的封面图有什么数学背景？
时间为什么用 12 进制？
离散型随机变量有没有概率密度？
如何克服粗心导致的计算错误？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
将一部分复变函数、傅里叶变换加入高考数学，一部分哈密顿力学拉格朗日变分法加入高考物理，大家是否赞同？这个含正弦函数的和式极限怎么求?
除了Weierstrass函数，还有哪些处处连续处处不可导的实变函数的具体例子？
2021年5月14日，著名数学家王元院士去世，他对中国数学界有哪些贡献？
伽罗华并没有接受完整的数学教育，为何能解决当时最难的数学问题？
一个多项式在满足什么条件时可以因式分解？能否给出证明（证法随意）?
∑ (1/n) 为何不收敛？
有哪些有趣的数学史？
我想了解一下：最小公倍数＝两数乘积 / 最大公因数，出自于哪里？
数学史上有哪些看似成立的算式形式猜想，最终被某个大数证明不成立？
数理特长生学医的话是人才浪费吗?
为什么数学 PhD 们喜欢围棋？
由AB＝BA＝O可以得出什么结论？
怎么建立复数与实数的一一对应？
为什么美国中小学生学的数学比我们简单，美国人却还能做出超级牛的东西？
我感觉我对数学的求知欲在下降，怎么办？
数学中有哪些看起来很不可思议的知识？
一个拓扑流形的不同微分结构是否一定给出在拓扑上同胚的切丛？
有没有处处不可导的凸函数？
除了 1 和 144，还有哪个斐波那契数是平方数?
没有基的线性空间，是否可以构造，如何构造？
内心随便想一个正整数，让别人来猜，猜对的机率是多少？
如何证明这个与树有关的递推式？
这道定积分怎么算（据说是某211期末考试题）？
你对俄罗斯和法兰西数学物理教材有哪些看法？
你在生活中用过最高端的数学知识是什么？
阿⻄莫夫三定律，会不会被打破？
如果1+1=3，这个世界会怎么样？
如何将条件收敛级数 1-1+1/2-1/2+1/3-1/3+1/4-1/4+...证其发散？
离散型随机变量有没有概率密度？