Khác biệt giữa bản sửa đổi của “Lý thuyết đồ thị”

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> 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'').