ОПРЕДЕЛЕНИЕ. Граф G1 = (V1,U1) называется подграфом графа G2 = (V2, U2), если V1 V2 и

Граф G ₁ = (V ₁, U ₁) называется подграфом графа
G ₂ = (V ₂, U ₂), если V ₁ V ₂ и U ₁ U ₂.

Например, граф G ₁, приведенный на рис. 5.8., является подграфом графа G ₂.

a G ₂ a G ₁

B b

C c

d

Рис. 5.8.

Удаление из графа G некоторой вершины v, степень которой равна 2, - это замена удаляемой вершины и двух выходящих из нее ребер на одно ребро, соединяющее отличные от v концы удаленных ребер.

Процесс последовательного удаления из графа G одной или нескольких вершин степени 2 называется стягиванием этого графа. Обратная операция для удаления вершин степени 2 называется разбиением ребер.

Заметим, что операции удаления из графа вершин степени 2 и разбиения ребер сохраняют свойства графов быть планарными или непланарными.