Opened 11 years ago

Last modified 11 years ago

## #7476 closed enhancement

# Edge-disjoint spanning trees — at Initial Version

Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|

Priority: | major | Milestone: | sage-4.5 |

Component: | graph theory | Keywords: | |

Cc: | jason | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description

The theorem from Nash-Williams on the existence of k edge-disjoint spanning trees in a graph is both important, useful, and polynomial to compute. This could be implemented using the short proof described in the following article :

http://arxiv.org/abs/0911.2809

Or, if we achieve to eventually define in Sage a class Matroid, this could be done through the Matroid Union Theorem as presented in Schrijver's book.

**Note:**See TracTickets for help on using tickets.