Изменения

# Для каждого ребра <tex>(u,w)\in E(G)</tex> добавим в граф <tex>G^*</tex> две новых вершины <tex>e(u)</tex> и <tex>e(w)</tex>, соответствующие <tex>u</tex> и <tex>w</tex>, и соединим их ребром. В результате каждой вершине <tex>v \in V(G)</tex> будет соответствовать множество <tex>S(v) \subset V(G_f^*)</tex> такое что <tex>|S(v)|=deg(v)</tex>; Каждому ребру <tex>(u,w) \in E(G)</tex> соответствует ребро <tex>(e(u),e(w))</tex>, причем ни для каких двух ребер из <tex>E(G)</tex> концы соответствующих им ребер в <tex>G^*</tex> не пересекаются.

# Для каждой вершины <tex>v\in V(G)</tex> добавим в <tex>G^*</tex> новые <tex>deg(v)-f(v)</tex> вершин, образующие множество <tex>T(v)</tex>. Каждую вершину из <tex>T(v)</tex> свяжем ребром с каждой вершиной из <tex>S(v)</tex>. В результате для каждой вершины <tex>v \in V(G)</tex> Множество <tex>S(v)\cup T(v)</tex> образует полный двудольный граф.

{{Теорема