Determining the matching number of a graph given maximal matchings.

88 Views Asked by At

Let $G$ be a graph with maximal matchings $M_1$ and $M_2$, with $3$ and $6$ edges, respectively. Determine the matching number of $G$.

The only progress I've been able to make is that $M_1$ and $M_2$ are edge disjoint owing to the fact that $|M_2|=2|M_1|$. I'm thinking it has to do with the larger matching being an augmenting path of the smaller matching. Any help or hints would be appreciated!