图论中满足任意k个顶点度数和小于n−k时最大独立集α(G) > k的证明咨询

嗨，我来帮你完成这个证明，咱们用反证法一步步推导：

证明过程：反证法 #

首先，我们先假设要证的结论不成立，也就是 ( \alpha(G) \leq k )。这意味着图 ( G ) 中最大的独立集大小最多是 ( k )——换句话说，图中任意 ( k+1 ) 个顶点都不可能是独立集，也就是任意 ( k+1 ) 个顶点里至少存在一对相邻的顶点。

接下来我们结合题目给出的度数条件推导矛盾：

• 设 ( S ) 是图 ( G ) 中任意一个大小为 ( k ) 的顶点子集，根据题目条件，( \sum_{v \in S} \deg(v) < n - k )。
• 我们计算 ( S ) 中所有顶点在 ( V(G) \setminus S )（也就是不在 ( S ) 里的 ( n - k ) 个顶点）中的邻居总数，记为 ( N )。显然 ( \sum_{v \in S} \deg(v) = \sum_{v \in S} \deg_S(v) + N )，其中 ( \deg_S(v) ) 是 ( v ) 在 ( S ) 内部的邻居数，它的值肯定是非负的。
• 结合题目条件可以得到 ( N < n - k - \sum_{v \in S} \deg_S(v) )，因为 ( \sum_{v \in S} \deg_S(v) \geq 0 )，所以必然有 ( N < n - k )。

这个结论意味着什么呢？如果 ( V(G) \setminus S ) 里的每个顶点都至少和 ( S ) 中的一个顶点相邻，那邻居总数 ( N ) 至少是 ( n - k )，但我们刚推出 ( N < n - k )，这就说明 ( V(G) \setminus S ) 中至少存在一个顶点 ( u )，它和 ( S ) 中的所有顶点都不相邻。

那这样一来，( S \cup {u} ) 就是一个大小为 ( k+1 ) 的独立集，这和我们最开始假设的 ( \alpha(G) \leq k ) 完全矛盾！

所以我们的假设不成立，原结论 ( \alpha(G) > k ) 得证。

备注：内容来源于stack exchange，提问作者user1316777