一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
为什么我们可以用平面取一点来证明概率为零事件能发生？如何看待数学大神韦东奕的讲课方式难以理解学生纷纷退课，课堂教学应该采取什么样的互动方式？
为什么有理数 1/49 看起来这么像是个无限不循环小数？循环节在哪里？
怎样理解“范畴”？
现在还能通过自学成为数学家吗？
中心对称的汉字都有哪些?
放风筝时风筝线是弯曲的，这条曲线长什么样呢？
可不可以将所有无理数全都用 有理数·π 来表示？
这张图中能数出多少个三角形？
交换环的子环是否一定是交换环？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
能不能让两个与 π 无关的两个数之和等于 π？如果1+1=3，这个世界会怎么样？
深夜刷数学题是一种怎样的体验？
如何证明以下的这个组合恒等式？
123456789怎样运算等于1？
在数学中良序，偏序，全序三者之间的联系和区别是什么？
为什么做数学题不要轻易看答案？
大学数学具体学什么，以及相关的自学用书？
如何看待 Google 2004 年在硅谷公路旁一巨型广告牌上贴出的那道数学题用于招聘？
10000⁴ 和 4¹⁰⁰⁰⁰，怎样比较大小？
如何看待《中国学生所谓的数学牛逼》这篇文章？
如何在冰雹猜想上做出点成绩?
数学系的你，喜欢数学还是讨厌数学，还是毫无感觉？
学数学或物理学到 high 很刺激，是一种怎样的经历与感受？
高三生只对数学感兴趣，其他科都不喜欢，未来该怎么做？
如何证明n是2的幂?
算子代数是一门怎样的数学分支？学习算子代数需要怎样的基础？
这个不等式的证明方法有哪些？
数学的学习，是计算重要，还是理论学习重要？
如何求级数和1/（3^n-2^n）？
圆的面积 S 与半径的平方 R² 成正比，是从数学上的严格证明，还是一种数学直觉？
如何证明若行列式 D 中有两行元素分别对应成比例，则 D=0？
有哪些数学上的定理让你感觉「这不显然吗，这还用证明」？
有关大学物理推导的微分运算是否合理？
三门问题(蒙提霍尔悖论)变种，如果主持人不知道哪个门是汽车随便蒙门打开正好是羊这时观众还需要换门吗？
如何解决这个数学问题?
数学不需要依赖任何观测吗?
在没有能量损失的理想台球桌上任意击球，球是否最终必然进洞？
“不能被定义”是一种定义吗？
如何理解西安 8 岁神童自创奥数解题公式？