题目： 证明如下问题是NP-完全的： 输入：两个图G1 = (V1, E1) 和G2 = (V2, E2) ：预算b。 输出：两个节点集合V1’∈ V1 和V2’∈ V2和它们被移除后，将在两图中分别留下至少b个节点，且图的剩余部分完全一样 解析：
可将最大独立集问题归约到此问题，比如若要求任意图G（V, E）中大小为d的独立集，可以令G1 = （V, E），再令G2（V，∅）的顶点集与G相同，但是边集为空，也即是各个顶点相互独立。于是G1和G2存在着大小为d的公共子图，当且仅当图G存在着大小为d的独立集。
而由于最大独立集问题是NP问题，同理此问题也为NP问题。
