一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
一道三角最值如何思考？怎么积∫[0, 1] ln(1＋x²)/(1＋x) dx？
如何看待「搞积」这种现象？
如何证明悬链线图像是双曲余弦？
并非所有数学硕博都能从事科研，那么多数人继续读数学的理由为何？
请问高等代数判断多项式可约性的这一题要怎么入手？
清华踩线和复旦数学选哪个？
能将三角形面积分为两块面积比值是 k 的所有直线形成的包络线是什么样的？
2.什么是赫姆霍兹定理？
如何在田字格中作出一个正三角形？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
语言和数学，哪个产生早？为什么计算圆的周长与面积、球的表面积与体积，使用的都是 π，而不是三个不同的数？是偶然还是必然？
任意 ε＞0，a≤b＋ε 是否可推出 a≤b？
初中数学考19分还有救吗？
设A是一个3阶行列式，aij=1或-1，1≤i，j≤3，如何证明det（A）≤4？
现在的纯数学家们对于自然科学的关注大概是怎样的程度？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
德国与法国哪个国家数学贡献更大？
哪些伟大的数学家没有自己的传人或后代的？
为什么数学界研究人员作报告 PPT 风格都长得一样？
这个极限怎么求？求大佬帮忙？
为什么国产数分教材在定义函数f在x处极限的时候都要求函数f在x的去心邻域内有定义？
如何通俗地理解概率论中的「极大似然估计法」?
为什么 e^(iπ) + 1 = 0？
为什么宇宙当中的温度会有上下限？
怎样徒手开三次根号、四次根号？
为什么康德说数学是纯粹先天综合知识？
你所见过的最美的数学公式是什么？
黎曼猜想和哥德巴赫猜想有什么联系？
用 proof assistant/编程语言做数学科研的体验是怎样的？
如何证明对任意给定的正数e，存在M上的矩阵范数||A||，满足不等式||A||<=谱半径+e?
研究了一辈子学问却发现研究的方向错了，或当前流行的理论错了，你会有怎样的感想？你会怎样做？
为什么要构造出范德蒙行列式？
如果 a/b 是有理数，那么为什么圆周率不是有理数？
阿基里斯和乌龟的悖论真的不能用常规逻辑推翻吗？
这样的极限应该怎么去求解？
已知一个圆，一个点和一条直线，如何找到一个与圆相切过点且圆心在直线上的圆？
有哪些分析的恒等式有很深刻的数学背景？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
中国科学技术大学的数理课给你带来了什么？