Contraction of an even pair

Contraction of an even pair --- стягивание четной пары.

The contraction of an even pair [math]\displaystyle{ (u,v) }[/math] is an operation that consists in replacing the two vertices [math]\displaystyle{ u, v }[/math] by a unique vertex [math]\displaystyle{ t }[/math] whose neighborhood is [math]\displaystyle{ N_{G}(u) \cup N_{G}(v) - \{u,v\} }[/math]: the resulting graph is denoted by [math]\displaystyle{ G_{uv} }[/math]. Contracting an even pair preserves the chromatic number and clique number. Thus, successive contraction of even pairs could possibly be used to reduce a given graph [math]\displaystyle{ G }[/math] to a smaller, simpler graph with the same parameters [math]\displaystyle{ \chi }[/math] and [math]\displaystyle{ \omega }[/math]. In the case where the final graph is a clique, [math]\displaystyle{ G }[/math] is called even contractile; whenever this reduction can be performed not only for the graph [math]\displaystyle{ G }[/math] itself, but also for every one of its induced subgraphs, [math]\displaystyle{ G }[/math] is called perfectly contractile.