子图

普通子图给我们两次选择：先选留下哪些顶点，再选这些顶点间留下哪些边。诱导子图只给一次选择：顶点选定后，内部边便由母图唯一确定。因此寻找一条路径子图时可以忽略捷径；寻找诱导路径时，却必须检查选中顶点之间是否还存在额外边。

生成子图从另一方向固定了顶点集。生成树会删去多余边而保留所有顶点；诱导子图则先删去不关心的顶点，再让剩余边自动确定。看到“子图”二字时，先确认究竟固定顶点、固定边，还是两者都可选择，往往比计算本身更关键。

设 $G$ 是四边形 $abcda$ 再加对角线 $ac$。只保留四条外圈边得到一个生成子图 $C_4$，但它不是 $V(G)$ 诱导的子图，因为母图中的边 $ac$ 被遗漏。若取顶点集 $\{a,b,c\}$，先从母图逐条筛选两端都在集合中的边：$ab,bc,ac$ 留下，$cd,da$ 删除，因此诱导子图是三角形。若进一步删去 $ac$，便得到三点路径；这第二次自由删边使它成为普通子图，却失去诱导性。这里写 $ab$ 是无序边 $\{a,b\}$ 的简记。

在铁路网络中，“只看某一区域内的所有车站和区域内全部直达线路”对应顶点诱导子图；“保留所有车站，只选高速线路”更接近生成子图。前一种操作不会自行删掉区域内部不喜欢的线路，后一种操作也不能漏掉孤立在筛选结果中的车站。

图 minor理路图 minorGraph minor · Minor of a graph通过删顶点、删边和收缩边从原图获得的粗粒度图结构。比子图多允许收缩边。把三角形的每条边各细分一次得到六圈 $C_6$；它没有三角形子图，但收缩三条交替边后得到 $K_3$ minor。细分子图又允许目标图的边由内部顶点互不冲突的路径代替。普通子图、诱导子图、拓扑子图和 minor 因而是四种不同的包含证书。

空图是每张图的子图，图本身也是自己的子图。若讨论有向图或多重图，子图仍需继承母图相应的方向与边身份；本页公式针对有限简单无向图理路有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。，不能用集合 $F$ 自动表达两条端点相同的平行边。

某个性质若随删除顶点和边保持，称为子图闭性质。可平面性与二分性都具有这种闭性；连通性没有，因为删除一条桥就可能把图断开。若性质只保证在顶点诱导子图下保持，则称为诱导遗传性质，结论通常更弱。

一组顶点诱导完全图理路完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。时形成团理路团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。；诱导无边图时形成独立集。生成树理路生成树Spanning tree包含原图全部顶点且自身为树的子图。则是既覆盖全部顶点、又连通无圈的生成子图。这些常用对象分别固定了不同部分的子图自由度。

禁图定理必须写清允许哪种包含。Kuratowski 定理理路Kuratowski 定理Kuratowski's theorem有限图可平面嵌入，当且仅当不含 K5 或 K3,3 的细分子图。寻找 $K_5$ 或 $K_{3,3}$ 的细分子图，Wagner 定理寻找相应 minor；模式匹配中的 subgraph isomorphism 与 induced subgraph isomorphism 也会因“额外边是否允许”而得到不同答案。