# What structure does the set of all the matchings in a graph have?

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid.

I wonder what kind of structure the class of all the matchings in a graph can have? Or does it not have any usual structure?

It seems to me that it is close to but not a matroid. Is it the reason to study the class of all the sets of vertices covered by some matching, instead of studying directly the class of all the matchings?

Thanks!

-
When you say "matching", do you mean "partial (but potentially perfect) matching" or "only perfect matching"? –  Austin Mohr Nov 10 '12 at 20:36
any matching, not necessarily maximum/perfect. –  Tim Nov 10 '12 at 20:38

I think the main issue here is what the ground set of the matroid ought to be. The matching matroid has ground set $V(G)$, while each matching is a subset of $E(G)$. Unfortunately, in general, the set of matchings is not the set of independent sets of a matroid. It is of course a family that is closed under taking subsets, but the augmentation axiom fails. For example, if $G$ is path of three edges, and $M_1$ is the matching consisting of the middle edge, and $M_2$ is the matching consisting of the two end edges, then $|M_2|>|M_1|$, but we cannot augment $M_1$ via an edge in $M_2$.