= Edge contraction
{title2=$G/e$}
{wiki}
An <edge contraction> merges the two endpoints of an existing <edge>. For a finite <simple graph> $G$ and $e=uv$, replace $u,v$ by a new <vertex> $w$. Retain every <edge> with neither endpoint in $\{u,v\}$, and join $w$ to every member of
$$
N_{G/e}(w)=(N_G(u)\cup N_G(v))\setminus\{u,v\}.
$$
Here $N_G(u)$ and $N_G(v)$ denote the original open <graph neighbourhoods>, and $N_{G/e}(w)$ is the new <graph neighbourhood>. Remove the <self-loop> arising from $uv$ and merge duplicate <edges>, so the result $G/e$ is again a <simple graph>. This is not deletion of $uv$, which keeps both original <vertices>.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>{ref}
\Image[/graph-edge-contraction-common-neighbour-count.png]
{title=<Edge contraction> of a four-cycle and a <triangle in a graph>: <common neighbours> determine the lost <edge> count}
The left example contracts $uv$ in the <cycle graph> $C_4$ to give $\{wa,ab,bw\}$. Its endpoints have no <common neighbours>, so four <edges> become three. The right example contracts $uv$ in the <triangle in a graph> with <edges> $uv,ua,va$. Its endpoints have the single <common neighbour> $a$, so the two <edges> $ua,va$ become one <edge> $wa$: three <edges> become one.
For any such <edge contraction>, the exact counts are
$$
|V(G/e)|=|V(G)|-1,\qquad |E(G/e)|=|E(G)|-1-|N_G(u)\cap N_G(v)|.
$$
The contracted <edge> accounts for one loss. Each <common neighbour> $z$ contributes exactly one further loss, since $uz,vz$ become a single <edge> $wz$. All other <edges> correspond one-to-one to surviving <edges>. In particular the new <degree of a vertex> is
$$
\deg_{G/e}(w)=\deg_G(u)+\deg_G(v)-2-|N_G(u)\cap N_G(v)|.
$$
These formulas depend on simplifying to a <simple graph>; a <multigraph> convention that retains duplicate <edges> has different counts. In the six-<vertex> <branch set of a graph minor> diagram, contracting $12$ loses one <edge>, contracting the resulting $34$ loses two because of its <common neighbour> $A$, and contracting $56$ loses one. Hence its seven <edges> become the three <edges> of $K_3$: $7-1-2-1=3$.
An <edge contraction> can increase a <degree of a vertex> even while decreasing both total counts. For example, contracting $uv$ in the <tree> with <edges> $uv,ua,ub,vc,vd$ merges two <vertices> of <degree of a vertex> three into one of <degree of a vertex> four. This is the mechanism behind the distinction between a <graph minor> and a <topological minor>.
Back to article page
