CF1198C Matching vs Independent Set

You are given a graph with $ 3 \cdot n $ vertices and $ m $ edges. You are to find a matching of $ n $ edges, or an independent set of $ n $ vertices. A set of edges is called a matching if no two edges share an endpoint. A set of vertices is called an independent set if no two vertices are connected with an edge.

N/A

N/A

The first two graphs are same, and there are both a matching of size 1 and an independent set of size 1. Any of these matchings and independent sets is a correct answer. The third graph does not have a matching of size 2, however, there is an independent set of size 2. Moreover, there is an independent set of size 5: 2 3 4 5 6. However such answer is not correct, because you are asked to find an independent set (or matching) of size exactly $ n $ . The fourth graph does not have an independent set of size 2, but there is a matching of size 2.