如何理解图中最大连通分支阶数下界的相关定理？

咱们先把定理内容明确下来，再一步步推导、理解它的合理性：

定理原文 #

设$G$是一个有$n$个顶点（阶数为$n$，$n > 1$）、$e$条边的图，它包含$r$个连通分支（$r > 0$），每个分支的顶点数为$l_i$。如果$L$是所有连通分支里顶点数最多的那个分支的阶数，那么有如下不等式成立：
$$e/n \leq (L - 1)/2$$

等价变形：关联平均度 #

把上面的不等式两边同时乘以2，就能得到一个更直观的等价形式：
$$2e/n \leq (L - 1)$$
这里左边的$2e/n$是图$G$的顶点平均度——毕竟每条边会给两个顶点各贡献1个度数，总度数就是$2e$，除以总顶点数$n$，就得到了每个顶点的平均度数。所以这个不等式可以翻译成：图$G$中顶点的平均度，不会超过最大连通分支的顶点数减1。

为什么这个结论是“显然成立”的？ #

这其实是加权平均的基本性质带来的结果，咱们拆开来想：

• 对于任意一个连通分支来说，它的顶点数是$k$的话，这个分支最多能有$\binom{k}{2}$条边（也就是完全图的情况），此时这个分支里每个顶点的度数都是$k-1$，平均度就是$k-1$——这是这个分支能达到的最大平均度。
• 咱们的图里，最大的连通分支顶点数是$L$，所以它的平均度最多是$L-1$；而其他所有连通分支的顶点数$l_i$都不超过$L$，所以它们的最大平均度$l_i - 1$也都不超过$L-1$。
• 整个图的平均度，其实是所有连通分支平均度的加权平均（权重是每个分支的顶点数占总顶点数的比例）。而加权平均的结果，肯定不会超过所有分支里的最大平均度——也就是$L-1$。这么一来，整个图的平均度自然就小于等于$L-1$了，完全符合咱们之前得到的不等式。

内容的提问来源于stack exchange，提问作者Marco Bellocchi