1
$\begingroup$

This question should be an easy one :) I couldn't find it already in stackexchange so thought it would be worth asking.

As I understand it:

  • A Maximal Matching cannot be extended (i.e. it is not a subset of any other matchings).
  • A Maximum Sized Matching is if there are no larger matchings (i.e. no matchings with more edges).

So what exactly is the difference between these two? What does it mean that these two are "with respect to different partial orders"?

$\endgroup$
4
  • 2
    $\begingroup$ While I have no idea about matching theory, the following could be an answer: a maximal matching $M$ need not be maximum sized. For example, it could be possible that there is a matching $M'$ with more edges than $M$ but $M \not\subset M'$. The converse would seem to be true, however. $\endgroup$ May 12 '20 at 8:34
  • 2
    $\begingroup$ Consider the graph with four vertices $a,b,c,d$ and three edges $ab,bc,cd$. The matching $\{ab,cd\}$ with $2$ edges is a maximum matching; in this particular graph there is no matching with more than two edges. The matching $\{bc\}$, with only one edge, is a maximal matching but not a maximum matching. $\endgroup$
    – bof
    May 12 '20 at 8:46
  • $\begingroup$ Thank you both! Very helpful comments! If either of you want to post an answer your welcome to! $\endgroup$
    – JFreeman
    May 12 '20 at 9:35
  • 1
    $\begingroup$ As for your final question, a Maximal Matching is maximal with respect to set inclusion: $M \le M' \iff M \subseteq M'$. A Maximum Sized Matching is maximal with respect to cardinality: $M \le M' \iff |M| \le |M'|$. $\endgroup$ May 12 '20 at 15:20

Your Answer

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

Browse other questions tagged or ask your own question.