Matchings · Independent Sets and Covers

Lesson 7

Nikolai Chukhin · Alexander S. Kulikov

Problem. Check your intuition. Which of the (in)equalities below hold for any graph \(G(V,E)\) that has no vertices of degree zero?

Multiple choice

  1. \(\alpha(G) \le \alpha'(G)\)

  2. \(\alpha(G) \le \beta'(G)\)

  3. \(\alpha'(G) \le \beta'(G)\)

  4. \(\alpha'(G) \le \beta(G)\)

  5. \(\alpha(G)+\beta(G)=|V|\)

  6. \(\alpha'(G)+\beta'(G)=|V|\)