Lesson 9

Theorem (Gallai, 1959). For a graph \(G(V,E)\) without vertices of degree zero, the following equality holds: \[\alpha'(G)+\beta'(G)=|V| \ .\]

Proof. Take a matching \(M \subseteq E\) of size \(\alpha'(G)\). For each vertex not touched by this matching, add an adjacent edge to \(M\). This gives an edge cover: \[\beta'(G) \le |M|+(|V|-2|M|)=|V|-|M|=|V|-\alpha'(G)\ .\]

Take an edge cover \(F \subseteq E\) of size \(\beta'(G)\). From each component of the graph \((V,F)\) take one edge—this gives a matching \(M\). Since there are at least \(|V|-|F|\) components in \((V,F)\), \[\alpha'(G) \ge |M| \ge |V|-|F|=|V|-\beta'(G) \ .\]◼