Изменения
Нет описания правки
# Лапой называется индуцированный подграф $K_{1, 3}$ - вершина (центр лапы) и три её соседа, не связанные между собой. Докажите, что если $B$ - минимальный по включению барьер $G$, то каждая вершина $B$ - центр лапы в $G$.
# Докажите, что если $G$ содержит четное число вершин и не содержит лапы, то он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).
# Предложите алгоритм нахождения множества Татта в двудольном графе за $\mathcal{O}(nm)$.
