Рассмотрим 2-связный граф G на п вершинах и пусть п1 и п2 - это такие натуральные числа, что п1 + п2 = п. Широко известным фактом является то, что V(G) можно разбить на 2 таких связных множества V1 и V2, что | V11 = п1 и |V2| = п2. В 1994 году МакКуэйг и Ота сформулировали следующую гипотезу для 3-связных графов. Эта гипотеза упомянута в обзорной работе Мадера о связности.
Гипотеза. Пусть к G N. Тогда существует такое натуральное число п, что любой 3- связный граф G на не менее чем п вершинах содержит к-стягиваемое множество.
Из работ Мадера следует, что ответ на аналогичную проблему для п-связных графов с п ^ 4 является отрицательным. А именно, для любого к ^ 2 существует сколь угодно большой (по количеству вершин) п-связный граф G такой, что G не содержит связного множества W такого, что W| = к и G — W является (п — 1)-связным. Таким образом, вопрос остаётся открытым только для 3-связных графов.
Следующая теорема из устанавливает существование больших стягиваемых множеств в 3-связных графах.
Теорема 1. Пусть т ^ 5 - целое число, а G - это 3-связный граф, v(G) ^ 2т + 1. Тогда G содержит стягиваемое множество W такое, что т < W| < 2т — 4.
Утверждение гипотезы очевидно для к =1. Гипотеза доказана для к = 2 в, для к = 3 в, для к = 4 в, и для к = 5 в. Автор утверждает, что гипотеза доказана для к = 6. Разработанные в методы могут быть адаптированы для получения доказательства результата для к = 5, которое значительно проще и короче оригинального. Таким образом, мы докажем следующее.
Теорема 2. Пусть G - 3-связный граф и v(G) ^ 11. Тогда существует 5-стягиваемое множество в графе G, если G не является одним из графов, изображённых на рисунке 1.
Вдобавок, мы докажем, что утверждение гипотезы является верным, если минимальная степень графа ограничена снизу.
Теорема 3. Пусть G - 3-связный граф, пусть k ^ 5 - натуральное число и пусть v(G) > k + 3, 5(G) > + 2. Тогда существует k-стягиваемое множество в графе G.
По индукционному предположению, в графе G есть (k — 1)-стягиваемое множество. Пусть c = [^3"^]. Тогда k ^ 3c + 5, 5(G) ^ k — c. Следовательно, по Лемме 25, в графе G есть k- стягиваемое множество. □
