- 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.
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!