0
$\begingroup$
  1. Maximal and maximum matchings seem to be with respect to different partial orders, do they? In the set of all matchings in a graph, a maximal matching is with respect to a partial order defined by growing a matching, while a maximum matching is with respect to a partial order defined by its size.
  2. Wikipedia says:

    While a partially ordered set can have at most one each maximum and minimum it may have multiple maximal and minimal elements.

    But there can be several maximum matchings in a graph. What goes wrong?

Thanks!

1 Answers 1

1

What you call "with respect to a partial order defined by growing a matching" is usually referred to as "(partially) ordered by inclusion".

A maximum matching isn't defined with respect to a partial order defined by size. This is because a partial order requires $(a\le b\land b\le a)\Rightarrow a=b$, whereas two matchings may have the same size yet be different. Thus, it's only the sizes that are partially (in fact totally) ordered, not the matchings. There is indeed only one maximum size, but several maximum matchings may have it.

  • 0
    @Tim: It's a [preorder or quasiorder](http://en.wi$k$ipedia.org/wi$k$i/Preorder), a reflexive transitive relation that's not necessarily antisymmetric.2012-11-25