Операция введения ребра

Если и в графе , то граф , где , получен из графа введением ребра . В силу коммутативности операции объединения множеств последовательность операции добавления ребер в граф не зависти от порядка, в котором эти ребра добавляются в граф, т.е.

.

Операция введения вершины в ребро

Пусть некоторое ребро графа . Добавлением вершины в ребро называется операция, в результате которой получается два ребра: и , а ребро удаляется из графа .