Question

【题目】求最大实数，使得对任意阶简单图，有不等式，其中，为图的边数，为图中三角形的个数.

Answer 1

【答案】

【解析】

先证明一个引理.

引理 设阶简单图有条边，个三角形.则.

证明 因为阶简单图中，个三角形共有条边，且每条边至多出现在个三角形当中，所以，.

回到原题.

首先考虑特殊的阶完全图，有.

令，则.

下面用数学归纳法证明：对任意阶简单图成立.

当时，结论显然成立.

假设当时，结论成立.

当时，取为阶简单图中度数最小的顶点，设其度数为，并设余下的个点构成的简单图中有条边，个三角形.则由引理知.①

由归纳假设知.②

因为点度数最小，所以，.③

设与点相邻的个顶点之间连有条边，这条边每条和点都形成一个三角形.故只需证明

. ④

易知，，.⑤

因此，.

将式①、③代入上式得.⑥

又由式⑤知.⑦

由式②、⑥、⑦知式④成立，即当时，结论成立.

从而，对所有，结论成立.

因此，.