Войти
K5подразделение 12-вершинного коронного графа В теории графов гипотеза Кельмана – Сеймура утверждает, что каждая 5-вершина -связный граф, который не является плоским, содержит подраздел 5-вершинного полного графа K5. Он назван в честь Пола Сеймура и Александра Кельманса, которые независимо описали эту гипотезу; Сеймур в 1977 г. и Кельманс в 1979 г. Доказательство было объявлено, но еще не опубликовано.
Граф является 5-вершинно-связным, когда нет пяти вершин, удаление которых оставляет несвязный граф. Полный граф - это граф с ребром между каждыми пятью вершинами, и подразделение полного графа изменяет его, заменяя некоторые его ребра более длинными путями. Итак, граф G содержит подразделение K 5, если можно выделить пять вершин графа G, и набор из десяти путей, соединяющих эти пять вершин попарно, без каких-либо путей, имеющих общие вершины или ребра с друг друга.
На любом чертеже графа на евклидовой плоскости не менее двух из десяти путей должны пересекать друг друга, поэтому граф G, содержащий K 5 subdivision не может быть плоским графом. В другом направлении, согласно теореме Куратовского, граф, который не является плоским, обязательно содержит подразделение K 5 или полного двудольного графа K 3,3. Гипотеза Кельмана – Сеймура уточняет эту теорему, предоставляя условие, при котором может гарантированно существовать только одно из этих двух подразделений, подраздел K 5. В нем говорится, что если неплоский граф 5-вершинно-связный, то он содержит подраздел из K 5.
Связанный результат, теорема Вагнера, утверждает, что каждый непланарный граф, связанный с 4 вершинами, содержит копию K 5 в качестве второстепенного графа. Один из способов переформулировать этот результат состоит в том, что в этих графах всегда можно выполнить последовательность операций стягивания ребер так, чтобы результирующий граф содержал подразделение K 5. Гипотеза Кельмана – Сеймура утверждает, что при более высоком порядке связности эти сокращения не требуются.
Более ранняя гипотеза Габриэля Эндрю Дирака (1964), доказанная в 2001 году Вольфгангом Мадером, гласит, что каждый n-вершинный граф с как минимум 3n - 5 ребрами содержит подразделение K 5. Поскольку планарные графы имеют не более 3n - 6 ребер, графы с не менее 3n - 5 ребрами должны быть неплоскими. Однако они не обязательно должны быть 5-связными, и 5-связные графы могут иметь всего 2,5n ребер.
В 2016 году гипотеза Кельмана – Сеймура была доказана. утверждал Синсин Ю из Технологического института Джорджии и его доктор философии. студенты Давэй Хэ и Ян Ван. Серия из четырех статей, доказывающих эту гипотезу, появилась в Journal of Combinatorial Theory Series B.
