Vertex Contraction

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, ...].

REFERENCES

Pemmaraju, S. and Skiena, S. "Contracting Vertices." §6.1.1 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 231-234, 2003.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 91, 1990.