Minimal triangulation

Minimal triangulation --- минимальная триангуляция.

Given a graph [math]\displaystyle{ G }[/math] of treewidth [math]\displaystyle{ k }[/math], a triangulation of [math]\displaystyle{ G }[/math] into a triangulated graph [math]\displaystyle{ H }[/math] is such that the following three properties hold:

(1) the maximal clique size is equal to [math]\displaystyle{ k+1 }[/math],

(2) if [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are nonadjacent vertices in [math]\displaystyle{ H }[/math], then every minimal [math]\displaystyle{ (a,b) }[/math]-separator of [math]\displaystyle{ H }[/math] is also a minimal [math]\displaystyle{ (a,b) }[/math]-separator in [math]\displaystyle{ G }[/math],

(3) if [math]\displaystyle{ S }[/math] is a minimal separator in [math]\displaystyle{ H }[/math] and [math]\displaystyle{ C }[/math] is the vertex set of a connected component of [math]\displaystyle{ H[V \setminus S] }[/math], then [math]\displaystyle{ C }[/math] also induces a connected component in [math]\displaystyle{ G[V \setminus S] }[/math].

Every graph has a minimal triangulation.