# Finding the maximum matching of the graph

I have been having a little difficulty with the question below.

Given the following graph:

Give the maximum matching i.e a matching with the most edges.

My problem is that is it possible for there to be multiple possibilities for the answer? As you could have {(v1, v4),(v3, v6)} or {(v1, v6), (v2, v4)} etc. each of which have 4 edges.

• Ah, I was looking at it wrong I think. So the maximum could be: {(v1, v2), (v3, v5), (v4, v6)}. Thanks for the help Mar 25 '18 at 14:19

There are precisely two maximum matchings in that graph. Since there are matchings consisting of three edges (and this is the largest possible since there are six vertices), $v_1$ must be matched to either $v_2$ or $v_3$. If $v_1 v_2$ is in the matching, then $v_3 v_5$ and $v_4 v_6$ must be in the matching. If $v_1 v_3$ is in the matching, then $v_2 v_4$ and $v_5 v_6$ are in the matching. Thus there are exactly two maximum matchings.