一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
如何在数学试卷上调戏阅卷人？数学家们用不等式做什么？
数学 PhD 有很多内容要学习吗？
如何证明任何一复系数整式p(z)都可以分解成若干个(z-c)相乘的形式？
怎么做这道不等式的证明题？
能否以数学为基石，写出一篇优质的科幻小说？
数系从有理数扩充为实数的跨越有无产生一些问题？
为什么要把 mathematics 翻译成「数学」，导致中学生对「数字的学问」没兴趣？
为什么我国现在在数学IMO取得第一的成绩，但杰出数学家却几乎没有？
有哪些「这也能用数学证明」的事件？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
日本麻雀中，六巡和七巡后向听数的期望分别是多少？怎样证明 0.999… = 1？
请问这道代数不等式怎么证？
为什么 Mathematica 不能显示积分过程，即使它能算出最终结果？
数学专业学生，认真听讲、推导书上公式，但不做题，会出现什么问题？
关于数学有什么有趣的笑话？
为什么说用矩阵定义线性映射是一个糟糕的观点？
为什么人类可以长期使用不同数位进制，而丝毫不显得凌乱，还切换自如 ？
如何真正从本质上理解数学?
对「数学就是为了刷掉那 70% 的人」有什么感悟或亲身体会吗？
有没有可能把 π 或 e 等无理数当成 1，这样就能使许多定理显而易见？
请问这个完全剩余系的性质如何证明？
做学术需要搞清楚高级计量经济学里全部的数学原理吗？
数学史上有哪些看似成立的算式形式猜想，最终被某个大数证明不成立？
中学课本中有哪些显而易见的错误？
为什么物理学家往往比数学家更有人格魅力？
如何评价知乎用户@Aries？
是否存在一个复解析函数f(z)，使得对于正整数n，f(n)就是第n个质数？
会不会某个人已经证明了哥德巴赫猜想，却不愿意讲出来？
全国范围内有很多学生在初中或高中初阶就学（完）了高数吗？
如何求解满足条件的映射的个数？
如何评价第12届全国大学生数学竞赛初赛（数学类A组）试题？
在圆上选取n个点，两两连线，最多可以在圆内形成多少个交点？
为什么说连续映射是一个拓扑概念？？
有没有什么和“数学归纳法名字中虽然有归纳两字，却不是归纳推理，而是演绎推理”类似的数学例子呀？
如何解决下列的数列问题?
数学爱好者眼中的数学是什么样的？
圆周率已被算到31.4万亿位，科学家如此执着，到底为了什么？
求解决这道题目？
Γ（i）怎么算？