Maximal matching that is not a maximum matching
graph
Solution
You are right. The first graph is a maximal matching, because you can not add any more egdes to the solution. The second graph is a maximum matching, because it is (one of) the matching(s) with the highest possible sum of weights. The second graph is also a maximal matching.
Problem
Is above graph maxmial but not maximum? I went ahead and got a maximum, which is below. Am I understanding Maximal vs. Maximum correctly?