I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across [this one](http://www.cmm.uchile.cl/~rhoeksma/files/cornelissen_hoeksma_manthey_narayanaswamy_rahul_waanders-approximating_connected_graph_factors.pdf), which is concerned with that topic under the additional requirement, that the factor be connected. 


In it I found this statement: 



> 
> "In general, d-regular, spanning subgraphs (also called d-factors) of minimum weight can be found in polynomial time using Tutte’s reduction to the matching problem." 
> 
> 
> 


I could however not find online information about how Tutte reduced the minimum weight d-factor problem to the matching problem.  

  

  

**Question:** 


which online available documents describe the above mentioned Tutte-reduction, resp. can anyone explain it?



Tutte's Reduction of Minimum Weight d-Factors to Matching
Given a graph $G$ we construct $\hat{G}$ such that $G$ has a $d$-factor if and only if $\hat{G}$ has a perfect matching. For each vertex $x$ of $G$ we take $d$ vertices $x\_1, \dots, x\_d$ in $\hat{G}$. For each edge $e = \{x,y\}$ of $G$ we take two vertices $e\_x$ and $e\_y$ in $\hat{G}$. We then create for edges:


1. An edge between $e\_x$ and $e\_y$
2. An edge between $e\_x$ and $x\_i$ for $ 1 \leq i \leq d$.
3. An edge between $e\_y$ and $y\_i$ for $ 1 \leq i \leq d$.


If an edge $\{x\_i, e\_x\}$ shows up in a perfect matching of $\hat{G}$, then also an edge $\{y\_j, e\_y\}$ must show up. This corresponds to have the edge $e = \{x,y\}$ as part of a $d$-factor in $G$. If the edge $\{e\_x,e\_y\}$ occurs in a perfect matching of $\hat{G}$ this corresponds to the edge $e = \{x,y\}$ not being part of a $d$-factor of $G$.


**Edit:** I was able to track down the references to Tutte's reduction from the article linked in the question. The reduction above is essentially the same as the reduction in Lovász and Plummer's *Matching Theory.* If one has access to this book see 10.1, the reduction is slightly different because it is done in two steps ($f$-factor to $f$-matching to perfect matching). Figure 10.1.1 on page 386 in a nice example.


The original Tutte paper "A short proof of the factor theorem for finite graphs" can be found [online](http://web.eecs.umich.edu/~pettie/matching/Tutte-short-proof-of-factor-theorem.pdf). In this paper the reduction is complementary to the one above. If we want a $d$-factor and $v$ is a vertex of degree $d\_v$ we create $d\_v - d$ vertices. Again each edge is replaced with a length 3 path, but this time selecting to middle edge of the path corresponds to choosing the edge in the matching rather than omitting it.


