一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
数学有些疑惑，老是犯小错误，怎样才能避免低级错误？专业的数学家只擅长证明不擅长使用数学吗？
想问问各位大手子这个定理怎么证明，题目在补充里?
求使 y=sqrt(x+a)+sqrt(x+b) 成立的正整数对 (x,y) 的数量这一类的题如何解？
有什么著名的理论或者定理吗？
喜欢数学，但是脑子不好使，怎么办？
你见过哪些让你叹为观止的物理和数学问题的证明或计算方法（包括简单粗暴的数量级估算）？
被高数虐是一种怎样的体验？
请问这到微积分证明题题怎么证?？
a,b,c>0，且abc=1，怎样证明1/√(1＋8a)＋1/√(1＋8b)＋1/√(1＋8c)≧1？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
在三角形abc中，∠B=90°，点D在边BC上，∠BAD=2∠C，AC=12,DC=8求AB？数学中最完美的数是什么，还会有此类数出现吗？
如何看待某数学博士宣称传统中医完全是扯蛋？
如果炸弹每秒钟爆炸概率提高一点，从数学期望上来看最有可能在哪一秒爆炸？
这个荔枝弯曲的形状是否有曲线方程？
方程 x³+y³+z³=33 是否存在整数解？
对于数学研究生来说，（在你的方向）「打基础」到什么地步可以开始做研究了？
洗澡的时候突然论证出了1等于0，2等于0，所有数等于0，这个论证哪里错了呢？
三扇门的概率问题，直觉为什么会产生问题？
两个小数的积一定是小数吗？
你见过哪些构思巧妙，令你眼界大开的数学问题？
在一个球内任取n个点，则这n个点落在同一个半球内的概率是多少？
数学专业为什么没有那么多劝退贴？
如何定性定量运用数学语言描述修昔底德陷阱？
救命，现在我是考研阶段，在自习室看见一个男生?
什么是上极限？
从自然数 1 ~ n 中随机取 m（1≤m≤n）个，其中最大数的数学期望是多少？
数列「1，2，2，3，3，3，...」的通项公式是什么？
如何看待高中生声称证明哥德巴赫猜想？
红绿蓝三色是（唯一的）正交基吗？
北大数学系田刚的学问到底怎么样？
请问这个人的数学水平如何？
为什么∫x²/（√1-x²）dx用分部积分求不出来不定积分?
等词是否可以用属于来定义？
全体自然数的发散级数和等于负十二分之一代表了什么？隐藏了一个天大的秘密吗？
椭圆的周长如何计算？
作为统计的博士生，你都读过哪些对你影响深远的统计书籍？
可导，可微，可积，连续的关系是什么？然后，它们各自的充要条件是什么？
任给N个连续的整数，是否能从中找到一些数（至少一个），使得它们加起来是N(N+1)/2的倍数？
小学数学为什么不从集合论学起？