??这是什么奇怪的名字qwq。
??只为便于理解，没有苛求专业的定义。
简单无向图：不存在重边、自环的无向图。
\(\delta(G)\)：无向图 \(G\) 中结点的最小度数。即 \(\min\{d(u)|u\in V\}\)。
完全图：两两结点都有且仅有一条直接连边的无向图。拥有 \(n\) 个结点的完全图记作 \(K_n\)。
团：\(G\) 的生成子图且为完全图。
最大团：是团且结点数最大。
由于没有找到类似的定义，我们定义 \(M(G)\) 为 \(G\) 的最大团的结点数。
??本来是一道小升初题，不过为了方便叙述以及保护读者的自尊心，我们直接抽象为图论模型。
??给定简单无向图 \(G=(V,E)\)，其中 \(|V|=99,\delta(G)\ge67\)，求证 \(M(G)\ge4\)。
??小学二年级的知识呐！
??取 \((v_i,v_j)\in E\), 令:
??\(\because \delta(G)\ge67\Rightarrow d(v_i),d(v_j)\ge67\).
??\(\therefore |A|,|B|\ge66\).
??对于 \(A,B\), 有全集 \(I=\{v_k|v_k\not=v_i\land v_k\not=v_j\}\). 则 \(|I|=|V|-2=97\).
??\(\therefore |A\cap B|\ge\max\{|A|+|B|-|I|,0\}=35\).
??再取 \(s\in A\cap B\).
??\(\because|\complement_V(A\cap B)|\le64<66\le d(s)\).
??\(\therefore(\exists t\in A\cap B)\left((s,t)\in E\right)\).
??\(\therefore\) 此时 \(\{v_i,v_j,s,t\}\) 在 \(G\) 中的诱导子图是完全图.
??\(\therefore\delta(G)\ge4\). QED.
??当 \(|V|=1751,\delta(G)\ge1314\)，\(M(G)\ge5\)。
??留作习题owo！
??可以发现，由 \(|V|\) 和 \(\delta(G)\) 构成的分式似乎会与 \(M(G)\) 产生联系……
??对于任意简单无向图 \(G=(V,E)\)，有：
??令 \(n_0=\lceil\frac{|V|}{|V|-\delta(G)}\rceil\), 则只需证 \((\forall n\le n_0)(\exists K_n)\left(K_n\subseteq G\right)\) 即可.
??对 \(n\) 归纳证明:
\(1).\) 当 \(n=1\), 显然存在 \(K_1\), 成立.
\(2).\) 设 \(n=m-1<n_0\) 时存在 \(K_m\), 成立, 考虑 \(n=m\) 时:
??取任意 \(K_m\subseteq G\), 令为 \(K=(V_K,E_K)\). 不妨设在 \(G\) 中, \(v\in V_K\) 的结点为 \(v_1,v_2,\dots v_m\).
??令集合 \(\{A_m\}\), 其中 \(A_i~(i=1,2,\dots,m)\) 有:
??\(\because|V-V_K|=|V|-m,(\forall i)\left(|A_i|\ge\delta(G)-m+1\right)\).
??即全集大小为 \(|V|-m\), 每个集合大小不小于 \(\delta(G)-m+1\). 由集合交的最小大小公式 ( 自行脑补即可 ), 有:
??\(\because m<n_0-1\).
??\(\therefore m<\frac{|V|}{|V|-\delta(G)}\Rightarrow m(\delta(G)-|V|)+|V|>0\Rightarrow m\delta(G)-m|V|+|V|>0\).
??\(\therefore|\bigcap_{i=1}^mA_i|>0\).
??\(\therefore\exists s\in|\bigcap_{i=1}^mA_i|\). 此时 \(\{v_1,v_2,\dots,v_m,s\}\) 在 \(G\) 中的诱导子图构成 \(K_{m+1}\).
??\(\therefore n=m\) 时成立.
??由 \(1).~2).\) 原命题成立, QED.
??不知道这个结论对最大团算法有没有什么帮助w。
??本文命题及证明过程为笔者独立完成，目前没有在网上找到类似命题。如发现该命题或证明过程存在问题，或命题此前文献中出现，欢迎给笔者留言。
??然而一个初一（现在初二）学生的脑洞也不至于成 paper。
原文：https://www.cnblogs.com/rainybunny/p/13127275.html