Petersen's 2-factor theorem

[ncohen]

As the docstring says :

Petersen's 2-factor decomposition theorem asserts that any 2r-regular graph G can be decomposed into 2-factors. Equivalently, it means that the edges of any 2r-regular graphs can be partitionned in r sets C_1,\dots,C_r such that for all i, the set C_i is a disjoint union of cycles ( a 2-regular graph ).

As any graph of maximal degree \Delta can be completed into a regular graph of degree 2\lceil\frac\Delta 2\rceil, this result also means that the edges of any graph of degree \Delta can be partitionned in r=2\lceil\frac\Delta 2\rceil sets C_1,\dots,C_r such that for all i, the set C_i is a graph of maximal degree 2 ( a disjoint union of paths and cycles ).

Nathann

[rlm]

If you're introducing a new module in sage.graphs, the header of the file should be much more descriptive of what the module is for, etc... Take a look at some of the other files for examples.

I'm (personally) very curious about what else you plan on including in graph_decompositions...

The patch applies cleanly, and the code looks good. Once again, I'd like to see a little more examples in the documentation.

[ncohen]

Hello !!!

As mentionned, I moved this function toward graph.py, and will patiently wait for the splitting of graph.py to begin creating new files.. :-)

(please do not forget to install GLPK or CBC before testing it because of #7734)

Nathann

[ncohen]

I tried to find another example, but could not find any interesting/funny one (the theorem and its proof by themselves are enough to make me laugh :-) ). If you can think of a good one, just tell me and I'll add it :-)

Nathann