Guichard-Combinatorics-Graph-Theory · Problem 4.5.2

Systems of Distinct Representatives

Mathematics — Probability · 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