补图

给定一个简单无向图，补图保持顶点不变，把原来没有边的不同顶点对连起来，并去掉原来已有的边。它可以表达“没有直接关系”的配对。

定义和例子

设 $G=(V,E)$ 是有限简单无向图。它的补图 $\bar{G}=(V,\bar{E})$ 满足 $$\bar{E}=\{\{u,v\}:u,v\in V,u\ne v,\{u,v\}\notin E\}.$$ 同一个顶点不会与自身连边，这是简单图补图定义的一部分。对每一对不同顶点，恰有一个图包含连接它们的边。

例如 $V=\{1,2,3,4\}$，原图边集为 $\{12,23,34\}$，构成一条四顶点路径。六个可能的顶点对中，剩下的 $13,14,24$ 是补图的边。补图也形成路径：沿 $3-1-4-2$ 行走恰好使用这三条边。

左侧边为 12、23、34；右侧边为 13、14、24。

度数与边数

固定顶点 $v$。另外 $n-1$ 个顶点分别是它在原图或补图中的邻居，而且不会同时属于两组，因此 $${\mathrm{deg}}_G(v)+{\mathrm{deg}}_{\bar{G}}(v)=n-1.$$ 把全部不同顶点对分成原图的边和补图的边，得到 $$|E(G)|+|E(\bar{G})|=(\genfrac{}{}{0ex}{}{n}{2}).$$ 上例中两图各有三条边，合计为 $(\genfrac{}{}{0ex}{}{4}{2})=6$。对补图再取一次补图，会把每一对不同顶点的相邻状态翻转两次，因此 $\overline{\stackrel{‾}{G}}=G$。

团与独立集

如果一组顶点在 $G$ 中两两相邻，它们组成团；同一组顶点在 $\bar{G}$ 中两两不相邻，构成独立集。反过来也成立。由此可将寻找大团的问题转为在补图中寻找大独立集。

图与补图不必有相同的连通性：顶点数大于一时，若原图不连通，那么取自不同连通分量的任意两点在补图中相邻；同一分量内的两点也可通过另一分量的任一点在补图中连通。所以原图不连通时补图连通，但两者也可能同时连通，如上面的四顶点路径。