Edge contraction
In graph theory, an edge contraction is an operation that 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. Definition. The edge contraction operation occurs relative to a particular edge, formula_1. The edge formula_1 is removed and its two incident vertices, formula_3 and formula_4, are merged into a new vertex formula_5, where the edges incident to formula_5 each correspond to an edge incident to either formula_3 or formula_4. More  generally, the operation may be performed on a set of edges by contracting each edge (in any order). The resulting induced graph is sometimes written as formula_9. (Contrast this with formula_10, which means removing the edge formula_1.) 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. Formal definition. Let formula_12 be a graph ("or directed graph") containing an edge formula_13 with formula_14. Let formula_15  be a function that maps every vertex in formula_16 to itself, and otherwise, maps it to a new vertex formula_5. The contraction of formula_1 results in a new graph formula_19, where formula_20, formula_21, and for every formula_22, formula_23 is incident to an edge formula_24 if and only if, the corresponding edge, formula_25 is incident to formula_26 in formula_27. Vertex identification. 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 formula_4 and formula_29 are vertices of distinct components of formula_27, then we can create a new graph formula_31 by identifying formula_4 and formula_29 in formula_27 as a new vertex formula_35 in formula_31. More generally, given a partition of the vertex set, one can identify vertices in the partition; the resulting graph is known as a quotient graph. Vertex cleaving. 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 a reverse operation of vertex identification, although in general for vertex identification, adjacent vertices of the two identified vertices are not the same set. Path contraction. Path contraction occurs upon the set of edges in a path that "contract" to form a single edge between the endpoints of the path. Edges incident to vertices along the path are either eliminated, or arbitrarily (or systematically) connected to one of the endpoints. Twisting. Consider two disjoint graphs formula_37 and formula_38, where formula_37 contains vertices formula_40 and formula_41 and formula_38 contains vertices formula_43 and formula_44 . Suppose we can obtain the graph formula_27 by identifying the vertices formula_40 of formula_37 and formula_43 of formula_38 as the vertex formula_3 of formula_27 and identifying the vertices formula_41 of formula_37 and formula_44 of formula_38 as the vertex formula_4 of formula_27. In a "twisting" formula_31 of formula_27 with respect to the vertex set formula_60, we identify, instead, formula_40 with formula_44 and formula_41 with formula_43. Applications. Both edge and vertex contraction techniques are valuable in proof by induction on the number of vertices or edges in a graph, where it can be assumed that a property holds for all smaller graphs  and this can be used to prove the property for the larger graph. Edge contraction is used in the recursive formula for the number of spanning trees of an arbitrary connected graph, and in the recurrence formula for the chromatic polynomial of a simple graph. Contractions are also useful in structures where we wish to simplify a graph by identifying vertices that represent essentially equivalent entities. One of the most common examples is the reduction of a general directed graph to an acyclic directed graph by contracting all of the vertices in each strongly connected component. If the relation described  by the graph is transitive, no information is lost as long as we label each vertex with the set of labels of the vertices that were contracted to form it. Another example is the coalescing performed in global graph coloring register allocation, where vertices are contracted (where it is safe) in order to eliminate move operations between distinct variables. Edge contraction is used in 3D modelling packages (either manually, or through some feature of the modelling software) to consistently reduce vertex count, aiding in the creation of low-polygon models.