一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
预测一下到今年年底本轮中美搏弈的结果大概率是什么？有限域上为什么有x的m次方=e的解的个数不超过m？
抽象代数，如果G是一个奇数阶群，则G中的任何元都是一个唯一确定的元的平方，怎么证明，尤其是唯一性证明？
三门问题(蒙提霍尔悖论)变种，如果主持人不知道哪个门是汽车随便蒙门打开正好是羊这时观众还需要换门吗？
为什么没有以正右为 0 点并以逆时针转动的手表？
这句话对吗：平面直角坐标系中，在给定一个闭区间内存在一条可以被画出的曲线，此曲线定可以用某个函数表示？
高中数学有哪些像洛必达法则一样神一样有用的公式？
因子分析法求权重，两个指标可以用这个方法吗？这个方法的优势是什么？
n*n的棋盘填上1，2，...，n^2，使任意相邻（有公共边）格子里的数字之和不大于S，求S最小值?
成为一个数学家有多难？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
一个人要长到多高才可以让全世界的人们都可以看到他？一个数减去各位数字之和需要多少次减为 0？
数列1，22，333，4444……的通项公式是什么？
数学好的人去搞生物是种怎样的体验？
在微积分教材一开始直接引入 epsilon-delta 语言是否有利？
用三个汉字能描述的最大的数是多少？
x^11+x^7+1的因式分解是怎么想出来的？
1cm长度的线段上的点的个数，和1m长度的线段上的点的个数，哪个多？
祖冲之的圆周率的出处在哪里？
在微积分教材一开始直接引入 epsilon-delta 语言是否有利？
负数有没有阶乘，0 的阶乘为什么是 1？
在初等数学范围内，是否所有拥有递推公式的数列都可求对应的通项公式？
圆锥体内切球公式是怎么推导的?
1+0.1+0.01+0.001+0.0001... 一直下去会在实际中到达 2 吗？
如何证明有理数加法群不是有限生成群？
大家有人知道这个怎么解吗？
Minecraft 中只用一格水源，最多能灌溉多少耕地?
如何看待世界顶尖数学家、菲尔兹奖得主 Caucher Birkar 将全职加盟清华大学？
我在知网的《哥德巴赫猜想》简单证明能否被数学权威发现？
你有没有什么天赋逐渐丧失的经历？
除了黎曼猜想，数学界还有哪些至今尚未得到证实的猜想？
国外不用学数学的专业有哪些？
阿基里斯和乌龟的悖论真的不能用常规逻辑推翻吗？
什么是「斯特林公式」？
请问这道数学分析题目应该怎么做呢？
为什么会有数学家反对对无穷集合使用排中律？
(xⁿ - 1)/(x - 1) = y² 这个不定方程蕴含了哪些知识？
有没有什么可以让自己对数学感兴趣的书?
解微分方程为什么会出现个 e？
如何证明马尔科夫链一定会达到稳态？