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