一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
为什么会有「男生比女生学数学更有优势」这一说法？PDE 中的先验估计是什么意思？
无限不循环小数 派 中可以出现连续的100个0吗？
为什么帕斯卡定理涉及的恰好是内接「六」边形？
这样是不是就可以把人类的所有图像内容穷举出来了?
如何考虑这个2022贺年题？
没有基的线性空间，是否可以构造，如何构造？
能不能出一道很难的数学题，答案是 235，宿舍当门牌用？
学数学学到什么程度怎样才算学好了？
请问这个极限怎么算 谢谢?
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
什么是「测度论」？C#为何属性和取值相同的dynamic对象的GetHashCode()相同，直接比较两者却又不同？？
数学专业本科生如何选择方向？
五子棋先下的一定赢吗？如何证明？
数学应该如何自学？
泊松分布和正态分布有什么内在联系？
如何让自己喜欢上数学？
各位积佬们这个积分有什么好的思路吗？
用分离变量法来解 PDE 的合理性何在？
1 不可以被 3 除尽，但为什么圆可以被三等分？
如何看待Michael Atiyah爵士疑似证明黎曼猜想，并将在9月24日宣讲？
日本麻雀中，六巡和七巡后向听数的期望分别是多少？
能否通过列举一些代数式、方程加以分析、说明，直观解释阿贝尔定理（Abel–Ruffini th.）？
大家都是怎样学习高数（微积分）的?
等词是否可以用属于来定义？
范畴等价与范畴同构有什么本质上的区别？
什么是 Finsler Geometry？它与 Riemann 几何有什么关系？
遇到数理化难题容易头晕是智商低吗？？？
请问大家怎么看待北大数院（中心）赵强博士（已毕业）的学术水平，但他为何放弃数学研究了？
Alice 和 Bob 各有一个 0-9 的数，他们怎样能在不暴露自己数的前提下知道双方数字是否相同？
n的正因子个数d(n)有没有上界公式？
高中数学有没有可能在往后的人生中几乎用不到，如果有，那我们学习的意义是什么？
有哪些数学上的事实，没有一定数学知识的人不会相信？
格林公式的几何意义是什么？
将一部分复变函数、傅里叶变换加入高考数学，一部分哈密顿力学拉格朗日变分法加入高考物理，大家是否赞同？
为什么没有开区间上的 R 正常定积分的定义；开区间勒贝格可积，再加什么特殊条件，可得到开区间黎曼可积？
如何评价一些数学大佬在推导过程中的「我们不难发现…」、「显然有…」、「易得…」等语言?
「科普」数学的目的是什么？
如何只使用折叠的方法十等分一个线段或者绳子？
当抛掷一枚硬币时，前99次都为正面，那第一百次是正面还是反面？