Opened 13 years ago

Closed 13 years ago

# Petersen's 2-factor theorem

Reported by: Owned by: ncohen rlm major sage-4.3 graph theory sage-4.3.rc1 Nathann Cohen Robert Miller N/A

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

### comment:1 Changed 13 years ago by ncohen

• Description modified (diff)
• Milestone set to sage-4.3
• Status changed from new to needs_review

### comment:2 Changed 13 years ago by rlm

• Report Upstream set to N/A
• Status changed from needs_review to needs_work

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.

### comment:3 Changed 13 years ago by ncohen

• Description modified (diff)
• Status changed from needs_work to needs_review

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

### comment:4 Changed 13 years ago by 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

### comment:5 Changed 13 years ago by rlm

• Authors set to Nathann Cohen
• Reviewers set to Robert Miller
• Status changed from needs_review to positive_review

### comment:6 Changed 13 years ago by mhansen

• Merged in set to sage-4.3.rc1
• Milestone changed from sage-4.3.1 to sage-4.3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.