The contraction of a pair of vertices 
and 
of a graph, also called vertex
identification, is the operation that produces a graph in which the two nodes 
and 
are replaced with a single node 
such that 
is adjacent to the union of the nodes to which 
and 
were originally adjacent. In vertex contraction, it doesn't
matter if 
and 
are connected by an edge; if they are, the edge is simply removed upon contraction
(Pemmaraju and Skiena 2003, p. 231). Note that Skiena (1990, p. 91) is
ambiguous about the distinction between vertex contraction and edge
contraction, and confusingly refers to vertex contraction on vertices 
and 
as "contracting an edge 
."
The figure above shows a random graph contracted on vertices 
and 
.
Vertex contraction is implemented in the Wolfram Language as VertexContract[g,
v1,
v2, ...
].
