一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
二维傅里叶变换是怎么进行的？一根 1m 长的玻璃棒，摔倒地上断成 3 段，最短一段的平均值是多少？
100 瓶水其中有一瓶有毒，用老鼠试毒老鼠试后 7 天会死掉，需要多少只老鼠才能试出哪瓶水有毒？
关于数学扎心的句子有哪些？
数论问题困难性的根源是什么？
俄罗斯数学物理那么发达有什么原因？
概率论中，局部极限定理和积分极限定理不是一回事吗？
哪些数学命题可以用复数优雅地证明？
这个公式如何证明？
这个数列问题困扰我一段时间，大佬有没有好的方法呢？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
如何证明多项式 f(x)＝1＋x＋x²/2!＋x³/3!＋…＋x^n/n! 只有一个实数根？如何证明同一个魔方公式循环N遍后都会回到原状态？
数学中有哪些看起来很不可思议的知识？
无穷和等于三个数怎么解释？
研究了一辈子学问却发现研究的方向错了，或当前流行的理论错了，你会有怎样的感想？你会怎样做？
（纯）数学 phd 的你们和导师 meeting 的时候都聊些什么？
数学天才比常人强在哪里？
数学这种东西也许有用，但是，如何在现实生活当中用到它？
复数为什么比较不了大小？
1³+2³+3³+......+n³=多少？
是否存在实数a>1使得数列sin(a^n)收敛？
如何考虑这个2022贺年题？
这个极限怎么做呢？
请问这个极限如何计算？
古希腊的著作早期是否传入过中国？
C#为何属性和取值相同的dynamic对象的GetHashCode()相同，直接比较两者却又不同？？
圆周率 π 应该如何用极限或其它的微积分语言表示？是否可用极限或其它的微积分语言定义圆周率 π ？
一年级的孩子数学不好，想帮助他构建数学思维，有相关的书籍推荐吗？
每个长度无限的字符串里面一定有某个连续重复3次的字符串吗？
Cauchy定理的证明是否依赖于Jordan曲线定理？
为什么要用文字定义多项式，而不是直接将多项式函数定义为多项式？
一个有n条边的简单图最多有几个三角形?
最难的数学有多难？
中国在国际奥数比赛中，近些年几乎是压倒性的优势，可是为什么至今没有人获得菲尔兹奖？
请问为什么无穷个无穷小量的乘积不一定是无穷小量？
有哪些经典的反直觉数学结论？
1²＋2²＋……＋1005² 是奇数还是偶数？
算子代数是一门怎样的数学分支？学习算子代数需要怎样的基础？
为什么数学物理竞赛国家集训队只有两个女生，菲尔兹奖得主只有一个女性，诺贝尔物理学奖得主只有3个女性？
从 1~100 这 100 个数，按照怎样的顺序排列是最混乱的？