0
$\begingroup$

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

Given the following graph:

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.

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

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.

One must be careful when asking and answering questions like these to use indefinite articles like "a" and "an" instead of "the", since "the" connotes uniqueness.

$\endgroup$
1
  • $\begingroup$ @mrtoeknee since you are new to the site, allow me to remind you to accept answers that you feel suitably answer your question. $\endgroup$ Mar 25 '18 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.