О пороговых графах и реализациях графических разбиений

Тройка вершин $(x,v,y)$ в графе $G=(V,E)$ такая, что $xv\in E$ и $vy\notin E$, называется повышающей, если $\mathrm{deg}(x)\leq \mathrm{deg}(y)$ и - понижающей, если $\mathrm{deg}(x)\geq 2+\mathrm{deg}(y)$. Понижающим вращением ребра в графе $G$, отвечающим понижающей тройке $(x,v,y)$, называется преобразование графа, при котором ребро $xv$ заменяется на ребро $vy$. В работе доказано, что граф является пороговым тогда и только тогда, когда он не содержит повышающих троек вершин. Из этого результата вытекают три следствия. Графическое разбиение, отвечающее графу $G$, является максимальным графическим разбиением тогда и только тогда, когда граф $G$ является пороговым. Произвольное разбиение $\lambda$ является максимальным графическим разбиением тогда и только тогда, когда голова разбиения $\lambda$ равна его хвосту. Для произвольного графического разбиения $\mu$ все его реализации $H$ получаются с помощью конечных последовательностей понижающих вращений ребер из пороговых реализаций $G$ подходящих максимальных графических разбиений $\lambda$ таких, что $\lambda\geq\mu$.