一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
有没有哪些数学猜想是验证到很大的数以后才发现是错的？有没有双重否定不是肯定的情况？
我们为什么要学数学？学数学有什么意义？
如何证明：A*=A,则A的特征根为实数？
魔方运用了哪些数学原理？
何谓「做数学」？
使用微积分能否计算出一个玉米棒上玉米粒的个数？（看问题描述，被怼怕了）?
在科学研究里有没有需要对一个奇怪的数列求和的例子？
我本科是信息与计算科学专业，想考研但是不知道选什么专业，在纠结考数学还是计算机？
能否彻底从代数角度定义微分和积分？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
王茂泽宣称其破解世界著名难题「冰雹猜想」，他的证明正确吗？如何看待高中生声称证明哥德巴赫猜想？
国内大学数学系都上什么课程？
世界未解猜想需要学完所有数学才能破解吗？
弦理论专家爱德华 · 威滕对理论物理有哪些值得分享的独到见解？
科学是了解这个世界（宇宙）的唯一手段吗？
如何通俗易懂地解答双信封悖论？
Rokovsky函数(f(z)=1/2(z+1/z))分别将上半平面与下半平面映射成什么？
民科这个称呼是不是阶级固化的表现？阿贝尔，伽罗瓦当时看来是不是民科？民哲更有意思了？
线性代数有什么用？学习线性代数的意义在哪？
如何看待清华大学数学新领军计划和丘班综合测试？
为什么我们要学数学，长大之后数学能用在哪？
如何快速判断一个人的数学水平？
在圆上选取n个点，两两连线，最多可以在圆内形成多少个交点？
有没有可能把 π 或 e 等无理数当成 1，这样就能使许多定理显而易见？
有什么理论复杂但是实现简单的算法？
怎么证明圆锥曲线的光学特性？
请问这个极限式如何证明？似乎很像带 δ 函数的积分？
高次多项式不等式中「奇穿偶不穿」的原理是什么？求讲解，推导，数学证明。？
如何定义数？
数学该不该被踢出高考？数学有什么用处？
如果 a/b 是有理数，那么为什么圆周率不是有理数？
分家产的数学问题，17头牛老大1/2，老二1/3，老三1/9，是什么数学原理?
数学里的 e 为什么叫做自然底数？是不是自然界里什么东西恰好是 e？
一个有n条边的简单图最多有几个三角形?
如何评价数学家黎曼的成就与历史地位？
不规则四边形内如何获得面积最大的椭圆？
高考刚结束，有志于学习基础数学，假期想要自学一些大学数学内容，可以使用哪些书籍和习题？
如何评价2021年第62届IMO试题？
N个0和N个1排成一圈,平均能把这个圈分成几段?