关于证明任意图G的色数k≤(n+q)/2的技术求助

已知图G的色数为k（相邻顶点颜色不同的最少颜色数），团数为q（最大完全子图的大小），顶点数为n，且任意图满足k≥q。以下是不等式的证明：

我们用数学归纳法：

基例：n=q #

此时G是完全图，色数k=q，代入不等式得：
q ≤ (q+q)/2 = q，等号成立，不等式成立。

归纳步骤 #

假设所有顶点数小于n的图都满足不等式。考虑顶点数为n的图G：

1. 若G是完全图，则k=n=q，不等式变为n ≤(n+n)/2=n，成立。
2. 若G不是完全图，则存在两个不相邻的顶点v和u：
   • 考虑子图G-v，其色数χ(G-v)要么是k，要么是k-1。
   • 若χ(G-v)=k：根据归纳假设，k ≤ [(n-1)+q]/2 < (n+q)/2，不等式成立。
   • 若χ(G-v)=k-1：此时v的邻居数d(v)≥k-1（否则v可以用G-v着色中未使用的颜色，使χ(G)=k-1，矛盾）。同理，u的邻居数d(u)≥k-1。
   • 因为v和u不相邻，它们的邻居集合最多覆盖n-2个顶点（排除v和u自身），因此d(v)+d(u) ≤n-2。
   • 结合d(v)+d(u)≥2(k-1)，得2(k-1) ≤n-2 → 2k ≤n →k ≤n/2。
   • 又因为q≥1，所以n/2 ≤(n+q)/2，因此k ≤(n+q)/2，不等式成立。

综上，所有情况均满足k ≤(n+q)/2。

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