Một bài toán thường gặp, được gọi là [[bài toán đồ thị con đẳng cấu]] (''subgraph isomorphism problem''), là tìm các [[đồ thị con]] trong một đồ thị cho trước. Nhiều [[tính chất của đồ thị]] có tính ''di truyền'', nghĩa là nếu một đồ thị con nào đó có một tính chất thì toàn bộ đồ thị cũng có tính chất đó. Chẳng hạn như một đồ thị là [[đồ thị phẳng|không phẳng]] nếu như nó chứa một [[đồ thị hai phía đầy đủ]] (''complete bipartite graph '') <math>K_{3,3}</math> (Xem [[Bài toán ba căn hộ và ba hệ thống cung cấp năng lượng]] (''Three cottage problem'') hoặc nếu nó chứa [[đồ thị đầy đủ]] <math>K_{5}</math>. {{Xem thêm|Đồ thị phẳng}}. Tuy nhiên, bài toán tìm đồ thị con cực đại thỏa mãn một tính chất nào đó thường là [[bài toán NP-đầy đủ]] (''NP-complete problem'').
* [[bàiBài toán đồ thị con đầy đủ]] lớn nhất (''clique problem'') (NP-đầy đủ)
* [[bàiBài toán tập con độc lập]] (''independent set problem'') (NP-đầy đủ)
