Операция подразделения ребра

Пусть дан граф G=(V,E). Пусть ребро e=(v,w) – произвольное ребро графа G и .

Операция подразделения ребра e=(v,w) графа G состоит в построении графа , имеющего своими вершинами множество ,содержащего все ребра графа G, кроме выделенного e=(v,w), и плюс два новых ребра e =(v,v ), e =(v ,w), т.е. .

Определение. Граф H называется подразделением графа G, если он может быть получен из графа G путем применения конечного числа раз операций подразделения ребра.