一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
如何比较 π－2 与 lnπ 的大小？我能不能折出一根长3.3333.……米的小棍？
十进制有什么优点？为什么世界各地的数学不约而同的选择了十进制？
全国范围内有很多学生在初中或高中初阶就学（完）了高数吗？
二次型的意义是什么？有什么应用？
我是学数学的，每次看物理书总有种不严谨的感觉怎么办？
数学家和物理学家思考方式是什么？
f（x,y)->(x,y),是2维实数空间的 一一映射函数，f连续，f的反函数是否也连续，why？
如何看待 9 月 24 日 Michael Atiyah 在海德堡获奖者论坛上对黎曼猜想的现场宣讲？
999的99次方是什么概念？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
扔硬币，扔了三次反面，再次反面的概率真的是1/2吗？这种游戏规则是否有必胜策略？
极坐标下，形如 r = (sin(kθ)/sin((n + k)θ)) l 的曲线如何判断形状？
人们专门弄了一个自然对数函数的底数 e，是为什么？
这个极限怎么求？求大佬帮忙？
有数学问题在哪里请教？
如果从图中移去一个边的一个集合将增加亚图的数目时，被移去的边的集合就成为截。”那么，亚图是什么？截呢？
不查表，如何求 sin36 度？
实数中乘法不是加法的复合么？为什么乘法与加法并列提及？
该函数的最小值是多少?应该怎么解？思路是什么？
当我们说一个定理可以推出另一个定理的时候, 我们在说什么?
如何估计这个级数？
离散型随机变量有没有概率密度？
如何判断一个人适不适合学数学？
请问为什么 sin（A+B）=sinAcosB+cosAsinB，有没有详细推导呢？
科学为何有那么多近似计算？这样是不是和科学的严谨性相违背？
是否可以用纯数学手段配平化学反应式？
如何看待某数学博士宣称传统中医完全是扯蛋？
如何确定该双变量函数的所有间断点？
请试着论证下此问题是否条件充分，可解？
圆周率 π 应该如何用极限或其它的微积分语言表示？是否可用极限或其它的微积分语言定义圆周率 π ？
如何证明同一个魔方公式循环N遍后都会回到原状态？
怎样直观的理解「极大无关组」，以及极大无关组的求法？
学什么数学，为什么不直接学逻辑，为什么不把数学改成逻辑？
你有没有推导过一个复杂的却「贴近生活」的公式？
如果1+1=3，这个世界会怎么样？
如何推导下面这个等式？
数学在高考中占150分你怎么看？
欧拉到底有多厉害？
小学二年级数学老师，要求学生写 ÷ 时，必须横线尺子比着写、两个点特别圆，是不是有点过分？