一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
Fabrice Bellard 是个什么水平的程序员？数学工作者如何看待中医？
有哪些适合入门且较全面的运筹学书籍可以推荐一下吗？
被剑桥大学 deferred entry 应该接受吗？
语言和数学，哪个产生早？
求帮忙解一下这道题？
物理系学生感觉自己陷进数学里了该怎么办？
如何评价数学家黎曼的成就与历史地位？
北大数学天才韦东奕如果当初去了哈佛大学再回来，会怎么样？
假如我每次连续攻击目标所造伤害是上次次攻击的105%，我连续出拳一千次，能不能打穿坦克护甲？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
两个小数的积一定是小数吗？请问B项和D项有什么区别吗？
哪些看似与图论无关的问题可用图论模型解决？
中国大学数学与物理教育有哪些地方是三不管的?
「我对女生的兴趣，还没有我对数学的兴趣高。」这样的男生是怎样的性格？
质数在生活中有什么用？
高手大概率是谦虚还是傲慢的？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
如何评价hEzo？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
逆拓扑排序是拓扑排序的逆序嘛？
若随机实验存在数学期望，则一定满足强大数定律吗？
如何证明数列sinn^2发散？
本科阶段数学系的你的一天是怎么度过的？
如果让一个大学数学系的顶尖学霸去解一道高中极其困难的数学题，他还能解出来吗？
学数学专业是一种什么体验？
为什么我们可以用平面取一点来证明概率为零事件能发生？
为什么世界上最顶尖的科学家很多是单身汉？
数学草稿本需要很工整吗？
经济学是否适合文科生？
如何看待 Atiyah 对六维球面 S^6 上没有复结构的证明？
如何看待上海一城管为全球数学竞赛出题？你身边有哪些隐藏的「数学大神」？
上大学学了高等数学之后看高中的数学题是一种怎样的体验？
我有一个数学新发现，确定是新发现，确定是正确的，有什么平台可以出售转让变现？
数学论文的作者会意识到自己发表的结果实际上已经有人做出来过吗？
刚看了一个柯西不等式的推论，不知如何证明，希望得到解答?
如何推导以下几种连分数表示？
自增运算这道题怎么解？
为何可以用不动点法求数列通项公式，可不可以解释一下？
大家知道的最长（复杂）的公式是什么？