Edge contraction
= Edge contraction
{wiki}
Contracting an <edge> $uv$ identifies its endpoints, then removes loops and duplicate <edges> to produce a simple <graph>. It reduces the <edge> count by exactly $1+|N(u)\cap N(v)|$: one for $uv$, and one for each <common neighbour>.