Revision history [back]

I don't know how efficient this is, but to find all matchings with a fixed number of edges, you can do this:

sage: from itertools import combinations 
sage: g = graphs.PetersenGraph()
sage: E = [e[:2] for e in g.edges()]
sage: E # edges without the labels
[(0, 1),  (0, 4),  (0, 5),  (1, 2),  (1, 6),  (2, 3),  (2, 7),  (3, 4),  (3, 8),  (4, 9),  (5, 7),  (5, 8),  (6, 8),  (6, 9),  (7, 9)]

Now look for sets of n edges containing 2n different vertices, for example with n=5:

sage: [a for a in combinations(E, 5) if len(set().union(*a)) == 10]
[((0, 1), (2, 3), (4, 9), (5, 7), (6, 8)),
 ((0, 1), (2, 7), (3, 4), (5, 8), (6, 9)),
 ((0, 4), (1, 2), (3, 8), (5, 7), (6, 9)),
 ((0, 4), (1, 6), (2, 3), (5, 8), (7, 9)),
 ((0, 5), (1, 2), (3, 4), (6, 8), (7, 9)),
 ((0, 5), (1, 6), (2, 7), (3, 8), (4, 9))]