Корреляция между независимым набором и сопоставлением
Предположим, у нас есть неориентированный граф G = (V,E), и мы строим новый граф G ', где два узла смежны, если у них есть общий соседний узел в G. Может ли кто-нибудь объяснить, почему следующие утверждения верны, если у нас есть такой конструкция G '?
Если у G есть независимый набор размера n, то у G 'есть соответствие размера n. Если G 'имеет соответствие размера n, то G имеет независимый набор размера n.
К сожалению, у меня нет идеи для этой проблемы