一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
这道定积分如何解决呢？数学上一共有多少维度?
格林公式教材上的证明是否存在漏洞？
如何评价2021年第37届全国中学生数学竞赛决赛（CMO）？
矩阵思维是什么意思？
希尔伯特空间、内积空间的定义有什么关系和区别？
怎么建立复数与实数的一一对应？
世界上是不是不存在完美的圆？
现在的人工智能是否走上了数学的极端？
使用微积分能否计算出一个玉米棒上玉米粒的个数？（看问题描述，被怼怕了）?
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
利用无理数压缩数据是否可行？请问高等代数判断多项式可约性的这一题要怎么入手？
有n级台阶，每次可以走1～(n-1)的任意阶数，那么一共有多少种走法？
为什么数量级"皮可"很少使用？
(-1)^(0.4) 是否等于 (-1)^(2/5)？
河洛理数河洛真数河洛精蕴先看哪一本？
如何计算一局三国杀所进行的回合数的数学期望？
对于数学研究生来说，（在你的方向）「打基础」到什么地步可以开始做研究了？
智商的巅峰认证是什么？
σ-代数为什么叫代数？它有代数结构吗？
头发上的漩涡可以弄掉吗？
为什么行列式恰好能表示体积？
x+y+z=1 与x2+y2+z2=4 的交线 圆的半径怎么求？
明明现在用的微积分符号都是莱布尼茨发明的，为什么都说牛顿更伟大？
如何计算这个积分？
被高数虐是一种怎样的体验？
请问，一加一为啥等于二？
怎么证明勾股定理?
什么是上极限？
你知道哪些与数学有关的小故事？
无限大的围棋盘上某个子的存活概率是多少？
如何用数学证明活着就有希望？
大家有人知道这个怎么解吗？
随机变量服从正态分布，同时这个正态分布的均值也服从正态分布。这是什么分布？
有哪些经典的无解问题？
如何正确理解小概率事件，以及概率和哲学的关系？
如何计算函数 f(x)=log(x)/x 的 n 阶导数？
学数学学到什么程度怎样才算学好了？
两数列合并后有什么性质？
我想了解一下：最小公倍数＝两数乘积 / 最大公因数，出自于哪里？