maximum matching

• https://www.graphclasses.org/classes/par_13.html
  • maximum matching – A matching in a graph is a subset of pairwise disjoint edges (any two edges that do not share an endpoint). The parameter maximum matching of a graph $G$ is the largest size of a matching in $G$.
• unknown source
  • vertex cover upper and lower bounds maximum matching by a linear function – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
• assumed
  • maximum matching upper bounds maximum induced matching by a linear function – By definition
  • maximum matching on bipartite graphs upper bounds maximum matching by a linear function – by definition