形式陈述

图 $H$$H$ 是图 $G$$G$ 的子图，若 $V(H)\subseteq V(G)$$V(H)\subseteq V(G)$、$E(H)\subseteq E(G)$$E(H)\subseteq E(G)$，且边端点关系由 $G$$G$ 限制而来。诱导子图 $G[S]$$G[S]$ 包含端点都在 $S$$S$ 中的全部原图边；生成子图保留全部顶点。子图、minor 和细分子图是不同包含关系。

直觉

子图只允许删除顶点和边，不允许收缩边，也不必保留选中顶点之间的所有原边。

例子与边界

从三角形删除一条边得到路径子图，但不是三个顶点诱导的子图。收缩一条路径成单边得到 minor，未必是子图。讨论简单图、多重图或有向图时，端点和重边约定需与母图一致。

推论与应用

子图概念用于模式匹配、极值图论、连通性、平面性和局部结构分析。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Chs. 1–5。
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Parts I–V。