CODEWITHSUNDEEP
algorithmgraphmatchingindependent-set
Marc
Marc

Reputation: 301

Correlation between Independent Set and Matching

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

Upvotes: 1

Views: 88

Answers (0)

Related Questions