团与独立集

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

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

五圈 $C_5$ 没有三角形，故 $\omega (C_5)=2$；任取三个顶点总有一对相邻，故 $\alpha (C_5)=2$。它与自己的补图同构，团与独立集参数也随之相同。这种自补结构把两类对象的对偶直接画在同一张图上。

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

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

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

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

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

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

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

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

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