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?

5 points

  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|\)