一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
高中生能独自推导出 π 的计算公式是什么水平？大家都是怎样学习高数（微积分）的?
数学的符号系统有没有缺陷？
如何证明这道不等式？
有没有大神回答一下，级数中，比值判别法中的ρ是指什么？
零测集的子集是否可测？
有什么提高数学能力的书籍推荐吗？
阿⻄莫夫三定律，会不会被打破？
怎样的数学问题叫一个好问题？
为什么没有开区间上的 R 正常定积分的定义；开区间勒贝格可积，再加什么特殊条件，可得到开区间黎曼可积？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
请问如何把所有自然数均分成三类？在你的科研领域里，做得不错的年轻人都有哪些特征？
利用无理数压缩数据是否可行？
如何从深刻地理解随机过程的含义？
为什么不存在收敛速度最慢的级数？
数学上，「数」是怎么定义的？
一个袋子里有n个球，都是红球。现在拿一个球出来，放一个蓝的进去，重复n次过后红球占比？
偶极矩的“矩”在哪里？
请问这个函数与不等式问题该怎么解答？
麻生公开课教材问题如果a, b是两个相等的实数，那么a=0.是否正确？
数学专业是不是真的又难又脱离实际找不到工作啊⊙_⊙？
为什么规定 0 的阶乘为 1？
目前数学界有多少种运算方式?
怎样证明 0.999… = 1？
如何用组合数学证明 (n²)! 能被 (n!)^(n＋1) 整除？
一粒谷子不算谷堆，再加一点也不算，以此类推加到一万粒也不算，该如何解决这样的谷堆悖论？
宁波大学的陈计教授是一个什么样的人？
击倒中国奥数队的几何题应该怎么解？
线性代数有什么用？学习线性代数的意义在哪？
a,b,c>0，且abc=1，怎样证明1/√(1＋8a)＋1/√(1＋8b)＋1/√(1＋8c)≧1？
小学奥数可以难到什么程度？
最小二乘法的本质是什么？
x^7+1=(x^4+x^2+x+1)(x^3+x+1) 是如何分解得到的呢？
环中不可逆元一定是零因子嘛？
如何证明以下恒等式?
怎么理解 Yang-Baxter 方程？
原命题与逆否命题真假性一定相同吗？
有哪些看起来很难但做起来很简单的数学题？
如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？
QQ 群为什么叫 QQ 群，而不叫 QQ 环，QQ 域或者 QQ 格？