I know how to prove the existence of a maximum matching such that any one particular vertex is saturated (assuming no isolated vertices). But I don't really have any idea how to do this one...
I know it is sufficient for us to show this for any maximal matching M (that is not also maximum). Currently I'm thinking of a proof by contradiction, we assume that for all maximum matchings M', there always exists a vertex that is saturated by M but not by M'. But I don't really know what to do after that, or if I'm on the right track...Kindly advise! Thank you!
I have found the solution but just in case anyone has the same question I won't be removing my question. A hint is to use Berge's Theorem: M is a maximum matching if and only if G contains no M-augmenting paths.