一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
数学和物理中这些符号到底念什么？来源是什么？导数 dy/dx 是不是一个整体符号？
两个有理数之间一定存在一个无理数吗？
两条直线方程相加的几何意义是什么？
如何理解数列极限的定义？
有哪些物理系鄙视数学系的经典桥段？
有哪些比较好的数学分析和高等代数的公开课（数学系）？
为什么数学教材里，学生首先学习的就是算术，却不学习作为基础的集合与逻辑？
专业的数学爱好者喜欢的是数学的什么（请看问题描述）？
近期汤加火山喷发喷出了多少立方千米喷出物？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
数学好的人去搞生物是种怎样的体验？这种游戏规则是否有必胜策略？
如果变量X Y独立怎么证明E(X+Y)=E(X)+E(Y),E(XY)=E(X)E(Y)？
为什么菲尔兹奖没有诺贝尔奖在公众的影响力大？
为什么九宫格外面一圈数字顺时针或逆时针排列组成的八位数都能被 11 整除？
每个长度无限的字符串里面一定有某个连续重复3次的字符串吗？
数学中有什么难以置信的结论？
正整数和正整数中的偶数哪个多（如何证明）？
数学的学习，是计算重要，还是理论学习重要？
头发上的漩涡可以弄掉吗？
这道组合难题怎么解?
比0.000······1更小的非0数，是什么？
现代理论物理的新成果中，有没有因为使用不严格的数学最后被证明因此导致错误结果的案例？
如果高考允许以一百万人民币一分的价格无限量购买分数（收入归大学所有），那对社会会有怎样的影响？
在边长为 1 的正方形中随机取三个点，构成三角形的面积期望是多少？
数学是绝对真理吗？
自增运算这道题怎么解？
这个题怎么解，22题第二问有一步看不懂，红色笔圈？
可导，可微，可积，连续的关系是什么？然后，它们各自的充要条件是什么？
三角函数存在的意义是什么？
如图题，如何不用“强拆”的方式证明？
如何评价知乎用户 @证明 的哥德巴赫猜想证明？
数学学习与数学科研有多大区别？
逆拓扑排序是拓扑排序的逆序嘛？
如何通过卫星图判断这架飞机距离地面的高度？
怎样理解一个非常大的数？
皮尔逊系数为什么要中心化？中心化之后有什么好处？
如何求解这几道题?
偏序集与完备格？
你所在数学领域的 big picture 是什么？