backlog (работа над имеющимися решениями)

Теорема Геринга. Пусть и  — подмножества вершин графа , а Тогда верно одно из двух Утверждений:

Утверждение 1. В найдётся -разделяющее множество мощности

Утверждение 2. В найдётся непересекающихся путей из в (в том числе по вершинам множеств и

(a) Докажите, что оба условия не могут выполняться одновременно.

(b) Докажите, что если Утверждение 1 неверно, то верно второе, индукцией по количеству вершин. Преобразуйте граф так, чтобы -е утверждение не выполнялось, и при убирании некоторого ребра существовало -разделяющее множество , где Исследуйте множества и