无三角形简单图的最大度与最大独立集大小的关系及边数上界的证明问题

嗨，我来帮你梳理这两个针对无三角形简单图的证明思路，都是很经典的结论：

第一部分：证明最大度$Δ(G) ≤ β(G)$（$β(G)$为图的最大独立集大小） #

咱们用反证法来推导：
假设存在一个顶点$u$，它的度数$deg(u) = β(G) + 1$——也就是比最大独立集的大小还大。
$u$的所有邻居构成集合$N$，这个集合里有$β(G)+1$个顶点。但根据$β(G)$的定义，它是图中最大的独立集大小，所以$N$不可能是独立集（不然$β(G)$就不是最大的了），也就是说$N$里一定存在一对相邻的顶点。
这对相邻的顶点再加上$u$，就构成了一个三角形——可咱们的前提是图是无三角形的呀！这就产生了矛盾，所以假设不成立，也就证明了$Δ(G) ≤ β(G)$。

第二部分：证明边数$m ≤ \frac{|V(G)| \cdot β(G)}{2}$ #

这里咱们结合握手引理和第一部分的结论来推导：
握手引理告诉我们，图中所有顶点的度数之和等于$2m$（每条边会给两个顶点各贡献1个度数）。
我们取一个最大独立集$S$，它的大小是$β(G)$，剩下的顶点集合是$V \setminus S$，大小为$|V(G)| - β(G)$。根据第一部分的结论，每个顶点的度数都不超过$β(G)$，咱们可以直接推导：
总度数和$2m ≤ (|V(G)| - β(G)) \cdot β(G)$，展开后就是$2m ≤ |V(G)| \cdot β(G) - β(G)^2$。
因为$β(G)^2 ≥ 0$，所以$|V(G)| \cdot β(G) - β(G)^2 ≤ |V(G)| \cdot β(G)$，代入上式就能得到$2m ≤ |V(G)| \cdot β(G)$。
最后两边同时除以2，就得到了边数的上界：$m ≤ \frac{|V(G)| \cdot β(G)}{2}$。

备注：内容来源于stack exchange，提问作者Steve M.