Subscribe to the weekly news from TrueShelf

0

Saturated vertices and Maximum matchings

Let \(S\) be a set of vertices saturated by a matching \(M\) in a graph \(G\).

  • Prove that some maximum matching also saturates all of \(S\).

  • Must the statement be true for every maximum matching ?

Related Content