# Graph Condensation **An operation on a [[graph]] which removes an edge or a set of vertices.** ## Edge contraction > [!Example] Edge contraction > Let $G = (V,E)$ be a graph containing an edge $(u,v)$ where $u\neq v$. > > **Edge contraction** is a [[function]] $f$ which maps every vertex in $V\setminus\{u, v\}$ to itself and maps $u$ and $v$ to a *new vertex* $w$. > > The new contracted graph is $G'=(V', E')$ where $V'=(V\setminus\{u,v\})\cup\{w\}$ and $E'=E\setminus\{(u,v)\}$. > > Additionally, for every vertex $x\in V$ the corresponding vertex $x'=f(x)\in V'$ is incident to an edge $e'\in E'$ if and only if, the corresponding edge, $e\in E$ is incident to $x$ in $G$. Edge contraction is the *removal of an edge* $e=(u,v)$ from a graph and the *merging of vertices* $u$ and $v$ into a single vertex $w$, incident to which are any edges originally incident to $u$ and $v$. ![[EdgeContraction.svg|500]] The contraction of an edge can create a graph with [[Graph#Multigraph|multiple edges]] if the two vertices incident to the edge are originally *connected to the same vertex*. There is no standard for whether multiple edges are created or the resultant graph remains simple. ## Vertex contraction > [!Example] Vertex contraction > **Vertex contraction**, also known as **vertex identification**, is a more *generalised version* of edge contraction extended to *any pair* or [[subset]] of vertices. > > The contracted vertices are *merged*, the edges between them are *removed*, and all other vertices incident on the original vertices become *incident on the new vertex*. Edge contraction can be considered a special form of vertex contraction which is restricted to neighbouring vertices. Vertex contraction is the method by which a graph is [[Strongly Connected Component#Condensation graph|condensed]] into a [[directed acyclic graph]] of its strongly connected components.