Contracting edge, contraction of an edge

Contracting edge, contraction of an edge --- стягивание ребра.

If [math]\displaystyle{ G }[/math] is a graph and [math]\displaystyle{ (u,v) }[/math] is an edge of [math]\displaystyle{ G }[/math], the graph obtained by contracting edge [math]\displaystyle{ (u,v) }[/math] is the graph obtained from [math]\displaystyle{ G[V \setminus \{u,v\}] }[/math] by adding a new vertex [math]\displaystyle{ z }[/math] and adding edges [math]\displaystyle{ (z,w) }[/math] for all [math]\displaystyle{ w \in (N(u) \cup N(v)) \setminus \{u,v\} }[/math], where [math]\displaystyle{ N(u) }[/math] is the neighborhood of [math]\displaystyle{ u }[/math]. Contracting a subgraph means contracting all edges of it (the order in which the contraction is made is irrelevant). Note that multiple edges may appear.