团

图论中的团（clique）是一个顶点集合，其中任意两个不同顶点都相邻。等价地，该集合诱导出一张完全图。团把“每一对成员都有连接”写成一个全部顶点对都要满足的条件，强于只要求整体连通。

在边为 $ab,ac,bc,cd,de$ 的图中，$\{a,b,c\}$ 是三顶点团；$\{c,d\}$ 是两顶点团；$\{c,d,e\}$ 不是团，因为 $ce$ 不存在，尽管三点通过路径连通。

框中每对不同顶点之间都有边，因此构成三顶点团；尾部的三个点只连成路径。

极大团和最大团

对有限无向简单图 $G=(V,E)$，团 $C$ 满足 $$\mathrm{\forall }u,v\in C,u\ne v⟹\{u,v\}\in E.$$ 若不能再加入一个顶点而保持团性质，称为极大团；若顶点数在全部团中最多，称为最大团。最大团大小记为团数 $\omega (G)$。任意单顶点都是团；是否把空集也称团只影响空图的约定，通常令空图团数为零。

主例的 $\{c,d\}$ 已是极大团：$a,b$ 虽连接 $c$ 却不连接 $d$，$e$ 虽连接 $d$ 却不连接 $c$，无一点可加入。但它不是最大团，因为三角形 $abc$ 有三点。最大团必然极大，极大团却可能比最大团小很多；用“极大”代替“最大”会改变搜索问题。

主例的最大性证明

三角形 $abc$ 给出 $\omega (G)\ge 3$。若某个团含 $e$，它的其他顶点必须都在 $N(e)=\{d\}$ 中，故至多两点。若不含 $e$ 却含 $d$，除 $d$ 外只能取其邻居 $c$，也至多两点。剩下的团全部位于 $\{a,b,c\}$ 中，至多三点。因此 $$\omega (G)=3.$$ 这份分类同时覆盖“团使用尾部”和“团只在三角形中”的所有情况；仅展示一个三角形并不能排除别处存在更大团。

变式。 添加边 $ad,bd$，而保留原来的 $cd$。此时 $\{a,b,c,d\}$ 的六个顶点对都有边，形成 $K_4$。顶点 $e$ 仍只有一个邻居，不能加入四团，所以新团数为四。要从三团扩成四团，新顶点必须与原三团的三个成员全部相邻，少一条边都不够。

最大度和着色的两个界

若一个团有 $k$ 点，每个成员在团内就有 $k-1$ 个邻居，因此其全图度至少为 $k-1$。令最大度为 $\Delta (G)$，即得 $$\omega (G)\le \Delta (G)+1.$$ 主例最大度三给出团数至多四，但实际只有三，说明这个界不总紧。星图最大度可很大，团数仍只有二，因为叶子之间不相邻。

若给顶点正常着色，任意相邻顶点颜色不同。团中的每一对都相邻，所以 $k$ 团需要至少 $k$ 种颜色，从而 $$\omega (G)\le \chi (G).$$ 主例三色足够，例如 $a:1,b:2,c:3,d:1,e:2$，故两数都为三。但五顶点奇环没有三角形，团数为二；沿环交替使用两色会在闭合时冲突，需要三色，因此团数与色数一般不相等。区间图等特殊图类有额外结构使二者相等，不能推广到全部图。

与独立集及局部密度的区别

团在原图中要求所有顶点对有边，在补图中恰要求所有顶点对无边，因此 $$\omega (G)=\alpha (\bar{G}).$$ 这一等式给出团问题与独立集问题之间的转换。它不涉及连通分量：一个连通分量内部可以包含许多大小不同、互相重叠的极大团，主例中三角形与边 $cd$ 就共享顶点 $c$。

“边很多”也不同于“构成团”。四点图有六个可能边，只缺一条时密度为 $5/6$，仍不是四团。若应用允许少量缺边，应另行定义稠密子图或拟团标准，不能把精确定义中的“每一对”换成“多数对”。