Assume we have an undirected Graph G = (V,E) and we construct a new Graph G' where two nodes are adjacent if they have a common neighbor node in G. Can someone explain why the following statements are true if we have such a construction G'?
If G has an independent set of size n, then G' has a matching of size n. If G' has an matching of size n, then G has an independent set of size n.
Unfortunately I don't have an idea for this problem