maximum induced matching

• unknown source
  • maximum induced matching upper bounds diameter by a linear function – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
  • maximum independent set upper bounds maximum induced matching by a linear function – Each edge of the induced matching can host at one vertex of the independent set.
• https://www.sciencedirect.com/science/article/pii/0166218X9290275F?via%3Dihub
  • maximum induced matching – An induced matching in a graph G is a set of edges, no two of which meet a common node or are joined by an edge of G;
• assumed
  • maximum matching upper bounds maximum induced matching by a linear function – By definition