子图

普通子图允许在保留的顶点之间继续删边，因此表达“母图中能挑出这种连接模式”。诱导子图问得更严格：挑出一组顶点后，必须接受它们在母图中的全部内部关系。这一个量词差别决定了我们是在寻找某种稀疏骨架，还是寻找没有额外弦和额外冲突的完整局部场景。

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

设 $G$ 是四边形 $abcda$ 再加对角线 $ac$。只保留四条外圈边得到一个生成子图 $C_4$，但它不是 $V(G)$ 诱导的子图，因为母图中的边 $ac$ 被遗漏。若取顶点集 $\{a,b,c\}$，诱导子图 $G[\{a,b,c\}]$ 是三角形；只取边 $ab,bc$ 得到的三点路径仍是子图，却不是该顶点集的诱导子图。

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

图 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 也会因“额外边是否允许”而得到不同答案。