团与独立集

团与独立集观察同一组顶点内部的成对关系。团要求每一对都直接相邻，中间路径无法弥补缺边；独立集则要求一条内部边也没有。补图逐对翻转“有边/无边”，所以两类结构在同一顶点集上严格互换。

极大性对应一次贪心过程的终点：眼前没有单个顶点可以加入。最大性要排除图中所有其他候选，属于全局比较。真正的困难常在于撤销先前选择后寻找更大集合；给定候选的合法性反而容易检查。

五圈 $C_5$ 没有三角形且含有边，故 $\omega (C_5)=2$。要选独立顶点，每选一个就必须在顺时针方向留出至少一个未选顶点作间隔；选三个至少需要六个位置，因此 $\alpha (C_5)\le 2$，而任取一对不相邻点即达到等号。把顶点编号为 $0,1,2,3,4$，补图的圈可沿 $0,2,4,1,3,0$ 走完，所以它与原图同构。这同时核验了两类参数的补图对应。

在完全二分图 $K_{m,n}$ 中，任意跨侧边的两个端点组成大小为二的团，同侧则没有边。若 $m,n>0$，有

图可以拥有许多边，同时仍没有大团；边密度与团数之间没有简单的逐点换算。

三点路径 $x-y-z$ 中，单点 $\{y\}$ 是极大独立集，因为两个端点都与 $y$ 相邻；集合 $\{x,z\}$ 才是大小为二的最大独立集。这个最小反例已经足以推翻“贪心得到极大就等于求得最大”的推断。

空集与单点集按定义同时是团和独立集。连通顶点集只要求内部任意两点之间有路径，远弱于团的两两直接相邻。图论独立集的元素是顶点；拟阵独立集可以取别的底集，并额外满足交换公理，两种术语不能仅凭名称合并。

一个正常着色的每个颜色类都是独立集，因此色数公理库色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。等于把 $V$ 分割成独立集所需的最少份数。团中顶点两两相邻，必须使用不同颜色，于是

这个下界可能很松：从 $C_5$ 反复应用 Mycielski 构造，可以保持无三角形并让色数任意增大。

独立集与顶点覆盖公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。的补集对应把两个优化问题精确互换：给出最大独立集便得到最小覆盖，反之亦然。这个关系保持最优值，也保持每个具体可行解的补集，不依赖图是否二分。

最大独立集虽然是全局优化，也可能由小边界逐步求出。给定宽度 $k$ 的树分解，树宽动态规划公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions以最大独立集的完整逐袋计算，证明树分解边界状态、合并去重与回溯，并区分宽度、袋数和分解成本。按“当前袋中恰好选了哪些顶点”分类部分解，在每类中只保留最大大小。遗忘顶点时比较选与不选，合并两支时扣掉共同选中的袋顶点。六顶点图 $E=\{ab,ac,bc,cd,ae,be,ef\}$ 中，两支解 $\{a,d\}$ 与 $\{a,f\}$ 因共享 $a$ 合成大小三的 $\{a,d,f\}$；这个方法寻找的是最大解，而非一次贪心停止得到的极大解。

任意 $K_t$ 都迫使树分解公理库树分解与树宽Tree decomposition · Treewidth用按树组织的顶点袋覆盖图，并以最小最大袋大小衡量图偏离树结构的程度。中的某个 bag 同时包含其全部顶点，所以 $\mathrm{tw}(G)\ge \omega (G)-1$。Ramsey 定理公理库Ramsey 定理Finite Ramsey theorem足够大的有限结构中必然出现给定大小的同质子结构。则说明顶点数足够大时，图与补图不可能同时避开指定规模的团。

在冲突图中，可同时执行的一组任务对应独立集；在相识图中，两两直接相识的一组人对应团。建模时，相关性、共同邻居或经由第三方可达都不能替代边所表达的直接成对关系。