Подграфом данного графа называется граф, который получается из данного выкидыванием некоторых вершин и рёбер (дуг). Два неориентированных графа называются гомеоморфными, если один можно получить из другого следующими операциями: взять ребро и добавить посередине этого ребра вершину; взять вершину степени 2 и заменить её и выходящие из неё рёбра на одно ребро (заметим, что эти две операции взаимно обратны).