Lesson 8

Let's present several relations between the values \(\alpha(G)\), \(\alpha'(G)\), \(\beta(G)\), \(\beta'(G)\). We'll start with two minimax inequalities. The size of any vertex cover is not less than the size of any matching, since each edge in the matching must be covered by a new vertex, therefore \[\alpha'(G) \le \beta(G) \ .\] Similarly, the size of any edge cover is not less than the size of any independent set, since each vertex in the independent set must be covered by a new edge, therefore \[\alpha(G) \le \beta'(G) \ .\] Finally, it is easy to see that if \(I \subseteq V\) is an independent set, then \(V \setminus I\) is a vertex cover, therefore \[\begin{equation*}\alpha(G)+\beta(G)=|V| \ .\end{equation*}\] A similar relation for the dual parameters is more difficult to prove.