Edge contraction

Definition

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

The resulting graph is sometimes written as ${\displaystyle G/e}$. (Contrast this with ${\displaystyle G\setminus e}$, which means simply removing the edge ${\displaystyle e}$ without merging its incident vertices.)

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 ${\displaystyle G=(V,E)}$ be a graph (or directed graph) containing an edge ${\displaystyle e=(u,v)}$ with ${\displaystyle u\ne v}$. Let ${\displaystyle f}$ be a function that 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^{\prime }=(V^{\prime },E^{\prime })}$, where ${\displaystyle V^{\prime }=(V\setminus \{u,v\})\cup \{w\}}$, ${\displaystyle E^{\prime }=E\setminus \{e\}}$, and for every ${\displaystyle x\in V}$, ${\displaystyle x^{\prime }=f(x)\in V^{\prime }}$ is incident to an edge ${\displaystyle e^{\prime }\in E^{\prime }}$ if and only if, the corresponding edge, ${\displaystyle e\in E}$ is incident to ${\displaystyle x}$ in ${\displaystyle G}$.

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 ${\displaystyle v}$ and ${\displaystyle v^{\prime }}$ are vertices of distinct components of ${\displaystyle G}$, then we can create a new graph ${\displaystyle G^{\prime }}$ by identifying ${\displaystyle v}$ and ${\displaystyle v^{\prime }}$ in ${\displaystyle G}$ as a new vertex ${\displaystyle \mathbf{\text{v}}}$ in ${\displaystyle G^{\prime }}$. 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 ${\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^{\prime }}$ 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}$.

Repeated contractions

Given a finite set of edges, the order in which contractions are performed on a graph does not change the result (up to isomorphism). The result reduces to showing that ${\displaystyle G/e/(f/e)}$ is isomorphic to ${\displaystyle G/f/(e/f)}$ for two edges ${\displaystyle e,f}$ of ${\displaystyle G}$.