一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
高二了数学40多分还有救吗?有没有两个不相等的数 a 和 b，满足 a 的 b 次幂等于 b 的 a 次幂？
1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
统计学里有哪些振聋发聩颠覆三观的证明和定理？
从零开始学数学，有谁知道从何处入手，谢谢？
为什么手机计算器上50%+50%=0.75?
如何证明下列公式的通项公式呢？
请问《数字情种》是否可能翻拍成电影？
为什么笛卡尔之前没有人想到平面直角坐标系？
为什么尺规不能三等分一个任意角？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
经济学到底需不需要引入数学？请问如何理解极限的精确定义？
球面坐标计算三重积分公式怎么来的？
为什么 0.9 的循环等于 1？
围棋黑子贴7.5目，有数学理论依据吗？
怎样算原神up池到第x抽才出up角色的概率（1≤x≤180）？
工科跨考理论数学？有机会上好学校吗？
圆锥曲线中过任一顶点作相垂直的直线，过直线与曲线交点的直线过定点，这有什么射影几何的背景吗？
这张图片上的各位数学家分别是谁？
成功概率为 1% 的事件，理论上平均要尝试到第几次才能成功？
既然两个分数理论上来说可以无限接近，那么为什么还会出现无理数？
既然微分和积分互为逆运算，为什么积分比微分更难求解？
怎么看待考研数学老师李林「神押题」？
作为学数学的人，你有哪些用于「双十一」购物的方法？
为什么将 x²＋y²＝1 中 x 和 y 的指数换成大偶数，其图像会接近一个正方形？
如何用数学卖个萌？
高四了，数学只有七八十分，距离高考就剩一百多天了，真的很迷茫。该怎么提分啊?
大一数分高代需要努力才能学好是不是意味着天赋不够？
大数定律具体是个什么概念？
知乎上，女性是否较少回答技术/学术类问题，即使她从事的是相关行业？
这个求最值的问题有啥妙解嘛？
怎么看待「学数学没啥用，买菜难道还用得上微积分」的理论？
请问为什么数学中不废除除号“÷”？
PDE 中的先验估计是什么意思？
抽象函数2f(x)f(y)＝f(x+y)+f(x-y)的通式是什么？？
数学家下围棋，水平一定会很高吧？
1×0＝0 是因为 0 乘以任何数字都等于 0，还是因为 1 乘任何数字都等于那个数？
大一高数完全听不懂怎么办?
f（x,y)->(x,y),是2维实数空间的 一一映射函数，f连续，f的反函数是否也连续，why？
在没有能量损失的理想台球桌上任意击球，球是否最终必然进洞？