Изменения

# Для каждого ребра <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(gG)</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> образует полный двудольный граф.  {{Теорема|statement = Граф <tex>G</tex> имеет <tex>f</tex>-фактор тогда и только тогда, когда соответствующий данным графу и функции граф <tex>G^*</tex> имеет совершенное паросочетание.|proof = <tex>\Rightarrow</tex> Пусть граф <tex>G</tex> имеет <tex>f</tex>-фактор <tex>G_f</tex>. Построим паросочетание <tex>M</tex> для графа <tex>G^*</tex> следующим образом:# Для каждого ребра <tex>(u,w)\in G_f</tex> добавим в <tex>M</tex> соответствующее ему ребро из <tex>G^*</tex> . Теперь для каждой вершины <tex>v \in V(g)</tex> <tex>f(v)</tex> вершин из множества <tex>S(v)</tex> покрыты <tex>M</tex> .# Для каждой вершины <tex>v \in V(g)</tex> пусть <tex>R(v)\subset S(v)</tex> - множество вершин еще не покрытых <tex>M</tex>. <tex>R(v)\cup T(v)</tex> является полным двудольным графом, причем размер каждой из долей равен <tex>deg(v)-f(v)</tex>, следовательно этот граф имеет совершенное паросочетание <tex>M_v</tex>. Добавим каждое ребро из <tex>M_v</tex> в <tex>M</tex>.В результате каждая вершина в <tex>G^*</tex> покрыта <tex>M</tex>, следовательно <tex>M</tex> является совершенным паросочетанием. <tex>\Leftarrow</tex>  Пусть <tex>G^*</tex> имеет совершенное паросочетание <tex>M</tex>. Для каждой вершины <tex>v\in V(G)</tex> <tex>T(v)</tex> является независимым множеством и полностью покрыто <tex>M</tex>, следовательно множество <tex>R(v)\subset S(v)</tex> покрыто ребрами, концы которых лежат в <tex>T(v)</tex>, а значит каждая вершина из <tex>S(v)\setminus R(v)</tex> покрыта ребром, второй конец которого принадлежит <tex>S(w) : w \in V(G)</tex>, причем <tex>|S(v)\setminus R(v)| = deg(v)-(deg(v)-f(v))=f(v)</tex>. Поэтому если мы добавим в <tex>G_f</tex> все ребра соответствующие ребрам из <tex>M</tex> покрывающим <tex>S(v)\setminus R(v) : v \in V(G)</tex>, то есть все ребра из <tex>M</tex> концы которых лежат в множествах <tex>S</tex>, то степень каждой вершины <tex>v \in G_f</tex> будет равна <tex>f(v)</tex>, а значит <tex>G_f</tex> будет являться <tex>f</tex>-фактором.}} Из доказательства напрямую следует, что задача о поиске произвольного <tex>f</tex>-фактора графа <tex>G</tex> сводится к поиску совершенного паросочетания в графе <tex>G^*</tex>. Т.к. <tex>G^*</tex> в общем случае не является двудольным, для решения этой задачи можно воспользваться [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D1%8F_%D1%86%D0%B2%D0%B5%D1%82%D0%BA%D0%BE%D0%B2 Алгоритмом Эдмондса для поиска наибольшего паросочетания].