一个有n条边的简单图最多有几个三角形? 第1页
1
hao-di-fang-bug 网友的相关建议:
@猹猹 大佬的回答很完善了，我来个简单渐进版本的。我们设函数 表示一个有 条边的图的三角形数量的最大值。
引理：一个有 条边的图， 。
证明：
首先我们考虑这个图是个完全图，即存在 使得 。这个时候，三角形的数量
我们假设 是最小的正整数使得 。令 ，不难证明 （否则有： ，这与 是最小的矛盾）。于是我们可以得到：
inversioner 网友的相关建议:
之前没空想这个问题，不过我猜测就是“尽量组成完全图”时三角形最多。之后有时间就写个思路。
已经有大佬写了，我没什么新的想法，溜了（
1
相关话题
一个具有介值性的函数是否一定存在原函数？如何从代数和几何的角度分别理解矩阵？
一道三角最值如何思考？
关于物理旋转体（甜甜圈）模型体积的计算？
数学总是令我困惑，为什么可以这么做？
数列收敛的 ε-N 定义怎么理解？其作用是什么？
为什么国内做偏微分方程（PDE）的人这么多，而且招学生非常快？
数学需要回归简美贴近大众吗？
对任意多项式P_m(x)，是否一定存在Qn(x)，使P_m(x)Q_n(x)=Ax^(m+n)+B？
国内有哪些基础数学好的大学？
前一个讨论
请问(sinx)^3怎么用幂级数展开？
下一个讨论
如何计算以下的积分？
相关的话题
为什么中国人数理化学科成绩似乎秒杀外国人，但世界相关的（出名的）顶级的科学家几乎全是外国的？大学想学数学，没有竞赛基础，有哪些推荐的入门书籍？
有哪些无用的论文、研究？
怎么证明一条线是凸函数?
为什么lnΓ(x)~(x-1/2)lnx-x+1/2ln(2pi）？
有哪些不错的数学、物理类的「闲书」？
高中数学有哪些像洛必达法则一样神一样有用的公式？
金融数学偏金融还是偏数学？
俄罗斯数学物理那么发达有什么原因？
为什么经济学专业要学拓扑学？
请问这个函数与不等式问题该怎么解答？
如何证明R^2上的不可数集至少在一点附近局部不可数啊？
中国象棋的走法是有限的吗？如果有限，有没有先走或者后走的人必赢的可能？
是否存在一个「无法判定为有理数或无理数」的实数？
代数拓扑为什么研究同调？
如何评价2021年丘赛分析试题？
如何直观地理解群论？
这个积分有人会不呀 我想不通?
有哪些指标可以描述两个图（graph）的相似度？
葛军的高考数学卷子到底难在哪里？
格林公式为什么不对称啊？
为什么高中不直接开设高等数学、线性代数、概率统计这几门课呢？
如何证明圆周率中存在所有的 4 位数密码？
线性代数里面的矩阵是不是向量？假如是的话，为什么感觉这样的向量和几何里的向量有点不一样？
如何评价「泛函、映射、算子、变换都是函数，是搞数学的人骗普通人的把戏」这一说法？实际情况如何？
请问这道题用麦克劳林该怎么做?
矩阵思维是什么意思？
如何证明 1^2021＋2^2021＋…＋1000^2021 能被 7、11、13 整除？
高中数学有没有可能在往后的人生中几乎用不到，如果有，那我们学习的意义是什么？
为什么一个方程有复数解，数是一维的、二维的，还是？数学的性质特点是什么？数的维度是否暗示了能量的维度？