诱导子图

诱导子图（induced subgraph）由原图中的一个顶点集合唯一确定：选定顶点，并保留原图在这些顶点之间的全部边。与一般子图相比，它不允许再任意删去所选顶点之间的边；因此，它同时保留这些顶点原有的“相邻”和“不相邻”关系。

例如，设一个无向简单图的顶点为 $a,b,c,d,e$，边为 $ab,ac,bc,cd,de$。若只关注 $a,c,d,e$，删去 $b$ 及与它关联的 $ab,bc$，其余三条边 $ac,cd,de$ 都应留下。所得图是一条四顶点路径。这个例子展示了诱导子图的操作单位是顶点，哪些边消失由端点是否被删除决定。

从顶点选择到精确定义

设 $G=(V,E)$ 为无向简单图，即 $E$ 是 $V$ 中二元子集的集合。对 $S\subseteq V$，由 $S$ 诱导的子图记为 $$G[S]=(S,\{\{u,v\}\in E:u,v\in S\}).$$ 这一定义也覆盖 $S=\varnothing$ 的空图以及只含一个顶点的图。有时中文资料称其为导出子图。对有向图，使用相同原则，保留两个端点均在 $S$ 内的全部有向边，并保持方向。

选定顶点a、c、d、e。与未选顶点b关联的边随后一同删除。

G[S]保留所选顶点间的全部原有边，得到路径a—c—d—e。

通常记 $G-X=G[V\setminus X]$，称为删除顶点集 $X$。因此主例中的操作也可记为 $G-\{b\}$。若只删除边，则符号所表达的对象不同：$G-ab$ 保留所有顶点，只删除边 $ab$，一般不再是由全部顶点诱导的图，因为 $G[V]=G$。

固定顶点集时的唯一性

命题。 若 $H$ 是 $G$ 的子图，且 $V(H)=S$，则 $H$ 是 $G[S]$ 的生成子图；当且仅当它保留了 $G$ 在 $S$ 内的每条边时，才有 $H=G[S]$。

证明。 子图关系意味着 $E(H)\subseteq E(G)$。又因 $H$ 的顶点只有 $S$，其每条边两端都在 $S$ 内。所以 $$E(H)\subseteq \{uv\in E(G):u,v\in S\}=E(G[S]).$$ 两图顶点集相同，因此 $H$ 是 $G[S]$ 的生成子图。若每条内部原边都已保留，就有反向包含，边集相等；反过来，相等当然不能遗漏任何这样的边。

例如，在主例中选 $S=\{a,b,c\}$，诱导子图必须是三角形。仅留下 $ab,bc$ 所得的路径虽然是原图的子图，但不是原图的诱导子图：原图仍有 $ac$，而路径遗漏了这条内部边。“存在某个三顶点路径子图”与“存在某个三顶点诱导路径”是不同断言。

这也解释了诱导嵌入的条件。若把一个图 $H$ 的顶点一一映入 $G$，要让像构成诱导子图，就须对每两个不同顶点 $x,y$ 同时满足 $$xy\in E(H)⟺f(x)f(y)\in E(G).$$ 普通子图嵌入只要求正向蕴含。反向蕴含检查的正是原图中是否多出了边。

度数和路径发生的变化

顶点 $v\in S$ 在诱导子图中的度数，只计算留在 $S$ 内的邻居。记 $N_G(v)$ 为原图邻居集合，则 $${\mathrm{deg}}_{G[S]}(v)=\mathrm{\#}(N_G(v)\cap S)={\mathrm{deg}}_G(v)-\mathrm{\#}(N_G(v)\setminus S).$$ 主例中原度数依次为 $2,2,3,2,1$。删除 $b$ 后，$a$ 失去邻居 $b$，度数由二变一；$c$ 也失去 $b$，由三变二；$d,e$ 不变。所得序列为 $1,2,2,1$，和为六，恰好是三条边数的两倍。

诱导操作保留边关系，却不保证保留原图中的距离。原图中 $a$ 到 $e$ 有路径 $a,c,d,e$，但若改选 $T=\{a,c,e\}$，则 $G[T]$ 只有边 $ac$，顶点 $e$ 孤立。一般而言，诱导子图中的每条路径都是原图路径，所以在两点仍连通时，它们在诱导子图中的最短距离不小于原距离；删除顶点可能使距离增加，甚至使路径完全消失。

变式。 在同一原图中选 $U=\{a,b,d\}$。正确边集只有 $\{ab\}$，不是把路径 $b,c,d$ 缩成一条 $bd$ 边。诱导子图不创造捷径；“删除一个中间顶点再把其邻居连接”是另一种图操作。

逐次诱导与补图

若 $T\subseteq S\subseteq V$，则 $$(G[S])[T]=G[T].$$ 证明可逐边进行：不同顶点 $u,v\in T$ 在左图相邻，当且仅当它们在 $G[S]$ 相邻；因它们已在 $S$ 内，这又当且仅当它们在 $G$ 相邻。这恰为右图的边条件。因而分两次删除顶点与一次删除同一批顶点结果相同。

再令 $\bar{G}$ 为同一顶点集上的补图，不同顶点在补图中相邻恰好表示它们在原图中不相邻。于是 $$\overline{G[S]}=\bar{G}[S],$$ 左边补图的顶点全集取 $S$。对任意 $u,v\in S$，两边的边条件都是 $uv\notin E(G)$，所以等式成立。这里若忘记补图所相对于的顶点全集，就可能给左边错误地添回已删除的顶点。

一个性质若对某类图中的任意诱导子图仍成立，称为对诱导子图遗传。例如无环性和二分性是遗传性质：子图中的环也是原图中的环；原二分划分与所选顶点取交仍给出二分划分。连通性则不是，上面的 $G[\{a,c,e\}]$ 已给出反例。在图类理论中，“禁止某些诱导子图”表达的是哪些完整的局部邻接模式不能出现，而不只是禁止某些边的组合。