# find all matchings in a graph

Given a graph $G$, is it possible to ask Sage to generate all possible matchings of $G$? I know that G.matching() gives a maximum matching of $G$ and I also know that Sage has an iterator which finds all perfect matchings of $G$.

If no command exists which asks Sage to give me all possible matchings of $G$, does anyone have an idea of how to write a program to ask Sage to do this?

The documentation has matching_polynomial here; it's coefficients, ignoring the sign, tell you the number of matchings as the the number of edges increases. The matching polynomial for the Petersen graph is x^10 - 15

x^8 + 75x^6 - 145x^4 + 90x^2 - 6 which would be interpreted as 1 matching with 0 edges, 15 matchings with 1 edge, 75 matchings with 2 edges, 145 matchings with 3 edges, 90 matchings with 4 edges, and 6 matchings with 5 edges. It doesn't list the matchings but the documentation mentions an algorithm used to get the polynomial.Thank you for your comment. Yes, I was aware that Sage can compute the matching polynomial of a graph, which is why I am surprised that it cannot list the matching themselves if it can count them.

What I am trying to figure out now is the following: Given a the edge set E of a graph, how can I get Sage to give me all possible subsets of E which contain pairs with completely distinct entries, i.e., a matching.

I suppose you could work recursively: ask for all maximal matchings in

`G`

, and then ask for all maximal matchings in`G`

with a single edge removed, etc.A problem with my suggestion is that I don't know how to get Sage to tell me all maximal matchings. It produces a single one easily enough, but I don't know about all of them.