0
$\begingroup$

Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices? enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ What do you think and what did you try? $\endgroup$
    – Juho
    Nov 30, 2018 at 7:29
  • $\begingroup$ What do you mean by "minimum perfect matching"? $\endgroup$
    – xskxzr
    Nov 30, 2018 at 10:50
  • $\begingroup$ What do the labels on the edges mean? $\endgroup$ Nov 30, 2018 at 12:13

1 Answer 1

1
$\begingroup$

A perfect matching is one that includes every vertex so only graphs with an even number of vertices can have a perfect matching. If the number of vertices is odd, there is simply no perfect matching.

$\endgroup$
1
  • 1
    $\begingroup$ Sometimes one considers "almost perfect matchings" in which all vertices but one are matched. $\endgroup$ Dec 1, 2018 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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