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