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?

This problem can only be submitted at Cogniterra.

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