3 | | This theorem says that any 2r-regular graphs can be decomposed in 2-factors. If the graph is not regular and is of maximum degree Delta, then it can be decomposed as an union of Delta/2 disjoints (<=2)-factors. |

| 3 | Petersen's 2-factor decomposition theorem asserts that any |

| 4 | `2r`-regular graph `G` can be decomposed into 2-factors. |

| 5 | Equivalently, it means that the edges of any `2r`-regular |

| 6 | graphs can be partitionned in `r` sets `C_1,\dots,C_r` such |

| 7 | that for all `i`, the set `C_i` is a disjoint union of cycles |

| 8 | ( a 2-regular graph ). |

| 10 | As any graph of maximal degree `\Delta` can be completed into |

| 11 | a regular graph of degree `2\lceil\frac\Delta 2\rceil`, this |

| 12 | result also means that the edges of any graph of degree `\Delta` |

| 13 | can be partitionned in `r=2\lceil\frac\Delta 2\rceil` sets |

| 14 | `C_1,\dots,C_r` such that for all `i`, the set `C_i` is a |

| 15 | graph of maximal degree 2 ( a disjoint union of paths |

| 16 | and cycles ). |

| 17 | |

| 18 | |

| 19 | This patch both creates a new file in the graph directory, named graph_decomposition ( which will very soon contain many functions, do not worry about it !! ) into which is defined the function two_factor_petersen. |

| 20 | |

| 21 | As the moment, this patch requires many others which have not been merged : |

| 22 | * #6679 Edge coloring function |

| 23 | * #7270 Linear Programming class |

| 24 | * #7268 or #7333 as a LP solver |

| 25 | * #7364 eulerian orientation of a graph |

| 26 | |

| 27 | Perhaps the best thing to do is to review these patches before this very one. |

| 28 | |

| 29 | Nathann |