Combinatorics and Graph Theory · Problem 4.5.2

Systems of Distinct Representatives — David Guichard

Mathematics — Combinatorics · matchings

Problem

Show directly that the size of a minimum vertex cover in GG is the minimum value of n−k+∣⋃j=1kAij∣n - k + |\bigcup_{j=1}^{k} A_{i_j}|, as mentioned above.

Browse the problem library