contract | graph contraction | vertex identification

The contraction of a pair of vertices v_i and v_j of a graph, also called vertex identification, is the operation that produces a graph in which the two nodes v_1 and v_2 are replaced with a single node v such that v is adjacent to the union of the nodes to which v_1 and v_2 were originally adjacent. In vertex contraction, it doesn't matter if v_1 and v_2 are connected by an edge; if they are, the edge is simply removed upon contraction. Note that Skiena is ambiguous about the distinction between vertex contraction and edge contraction, and confusingly refers to vertex contraction on vertices v_1 and v_2 as "contracting an edge {v_1, v_2}."