Subdivision graph

Subdivision graph --- граф подразбиений.

A graph [math]\displaystyle{ G' }[/math] is a direct subdivision of a graph [math]\displaystyle{ G }[/math], if [math]\displaystyle{ G' }[/math] is obtained from [math]\displaystyle{ G }[/math] by subdividing an edge of [math]\displaystyle{ G }[/math] into two edges by inserting a new vertex: there is an edge [math]\displaystyle{ (u,v) \in E }[/math] with [math]\displaystyle{ E' = (E \setminus \{(u,v)\} \cup \{(u,x), (x,v)\} }[/math] and [math]\displaystyle{ V' = V \cup \{x\}, x \not \in V }[/math] ( subdivision of an edge). A graph [math]\displaystyle{ G' }[/math] is a subdivision of [math]\displaystyle{ G }[/math], if it is obtained from [math]\displaystyle{ G }[/math] by a sequence of direct subdivisions.