Edge contraction

Let ${\displaystyle G=(V,E)}$ be a graph (or directed graph) containing an edge ${\displaystyle e=(u,v)}$ with ${\displaystyle u\neq v}$. Let ${\displaystyle f}$ be a function which maps every vertex in ${\displaystyle V\setminus \{u,v\}}$ to itself, and otherwise, maps it to a new vertex ${\displaystyle w}$. The contraction of ${\displaystyle e}$ results in a new graph ${\displaystyle G'=(V',E')}$, where ${\displaystyle V'=(V\setminus \{u,v\})\cup \{w\}}$, ${\displaystyle E'=E\setminus \{e\}}$, and for every ${\displaystyle x\in V}$, ${\displaystyle x'=F(x)\in V'}$ is incident to an edge ${\displaystyle e'\in E'}$ if and only if, the corresponding edge, ${\displaystyle e\in E}$ is incident to ${\displaystyle x}$ in ${\displaystyle 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 ${\displaystyle v}$ and ${\displaystyle v'}$ are vertices of distinct components of ${\displaystyle G}$, then we can create a new graph ${\displaystyle G'}$ by identifying ${\displaystyle v}$ and ${\displaystyle v'}$ in ${\displaystyle G}$ as a new vertex ${\displaystyle {\textbf {v}}}$ in ${\displaystyle G'}$.[4] 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 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.

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.

Given two disjoint graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$, where ${\displaystyle G_{1}}$ contains vertices ${\displaystyle u_{1}}$ and ${\displaystyle v_{1}}$ and ${\displaystyle G_{2}}$ contains vertices ${\displaystyle u_{2}}$ and ${\displaystyle v_{2}}$. Suppose we can obtain the graph ${\displaystyle G}$ by identifying the vertices ${\displaystyle u_{1}}$ of ${\displaystyle G_{1}}$ and ${\displaystyle u_{2}}$ of ${\displaystyle G_{2}}$ as the vertex ${\displaystyle u}$ of ${\displaystyle G}$ and identifying the vertices ${\displaystyle v_{1}}$ of ${\displaystyle G_{1}}$ and ${\displaystyle v_{2}}$ of ${\displaystyle G_{2}}$ as the vertex ${\displaystyle v}$ of ${\displaystyle G}$. In a twisting ${\displaystyle G'}$ of ${\displaystyle G}$ with respect to the vertex set ${\displaystyle \{u,v\}}$, we identify, instead, ${\displaystyle u_{1}}$ with ${\displaystyle v_{2}}$ and ${\displaystyle v_{1}}$ with ${\displaystyle u_{2}}$.[5]