Edge contraction

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.

The edge contraction operation occurs relative to a particular edge, e. The edge e is removed and its two incident vertices, u and v, are merged into a new vertex w, where the edges incident to w each correspond to an edge incident to either u or v. More generally, the operation may be performed on a set of edges by contracting each edge (in any order).

As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph. However, some authors disallow the creation of multiple edges, so that edge contractions performed on simple graphs always produce simple graphs.

Let G=(V,E) be a graph (or directed graph) containing an edge e=(u,v) with u≠v. Let f be a function which maps every vertex in V\{u,v} to itself, and otherwise, maps it to a new vertex w. The contraction of e results in a new graph G′=(V′,E′), where V′=(V\{u,v})∪{w}, E′=E\{e}, and for every x∈V, x′=f(x)∈V′ is incident to an edge e′∈E′ if and only if, the corresponding edge, e∈E is incident to x in G.

Vertex identification (sometimes called vertex contraction) removes the restriction that the contraction must occur over vertices sharing an incident edge. (Thus, edge contraction is a special case of vertex identification.) The operation may occur on any pair (or subset) of vertices in the graph. Edges between two contracting vertices are sometimes removed. If v and v' are vertices of distinct components of G, then we can create a new graph G' by identifying v and v' in G as a new vertex v in G'.

Vertex cleaving which is the same as vertex splitting, means one vertex is being split into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. This is the reverse operation of vertex identification.

...
Wikipedia