Problem
COM-B2-M08-P002 Cover the Left Part
#2
★★☆☆☆ Level 2 of 5
In a bipartite graph, a matching covers all \(a\) vertices of the left part. Prove that the right part contains at least \(a\) vertices.
Different left vertices are matched to different right vertices.
Matching edges have no common endpoints. Therefore the \(a\) covered left vertices are joined to \(a\) distinct vertices of the right part. Hence the right part has at least \(a\) vertices.
Basic necessity for matching.