Файл:4-connected.jpg4-связный граф: при удалении любых трёх вершин, он остаётся связным.
В теории графов говорят, что нетривиальный граф Gвершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.
Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен.
Альтернативно граф, отличный от полного, имеет связностьk, если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным[1]. Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения.
Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему МенгераШаблон:Harv. Это определение имеет тот же ответ: n − 1 для связности полного графа Kn[1].
1-связный граф называется также связным, 2-связный граф называется двусвязным, 3-связный граф называется, соответственно, трисвязным.
