Свя́зность гра́фа, одна из топологических характеристик графа. Граф называется связным, если для любых его вершин $u$ и $v$ существует цепь, соединяющая эти вершины. Числом вершинной связности графа $G$ (обозначение $\varkappa(G)$) называется наименьшее число вершин, удаление которых (вместе с инцидентными им рёбрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом рёберной связности (обозначение $\lambda(G)$) называется наименьшее число рёбер графа $G$, удаление которых приводит к несвязному графу. Граф $G$ называется $k$-связным, если $\varkappa(G)\geqslant k$, и $k$-рёберно связным, если $\lambda(G)\geqslant k$. Максимальный по включению $k$-связный подграф графа $G$ называется его $k$-связной компонентой; 1-связная компонента называется компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надёжности этих сетей.

В теории графов изучаются способы установления связности графов, условия, при которых граф является $k$-связным или $k$-рёберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если $\delta(G)$ – минимальная степень вершин графа $G$, то справедливы следующие неравенства: $\varkappa(G)\leqslant\lambda(G)\leqslant\delta(G)$.

Для любых целых $a,b,c$ ($0<a\leqslant b\leqslant c$) существует граф $G$, у которого $\varkappa(G)=a$, $\lambda(G)=b$, $\delta(G)=c$. Если граф $G$ имеет $n$ вершин и $\delta(G)\geqslant\left[\dfrac n2\right]$, то $\lambda(G)=\delta(G)$. Говорят, что множество $S$ вершин, рёбер или вершин и рёбер разделяет вершины $u$ и $v$, если $u$ и $v$ принадлежат разным компонентам связности графа $G-S$, полученного из $G$ удалением элементов множества $S$. Справедливы следующие утверждения.

Наименьшее число вершин, разделяющих две несмежные вершины $u$ и $v$, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих $u$ и $v$. Граф $G$ является $k$-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере $k$ вершинно непересекающимися цепями. Аналогичные теоремы справедливы и для рёберной связности. Граф $k$-рёберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере $k$-рёберно непересекающимися цепями. Множество рёбер, удаление которых приводит к несвязному графу, называется разрезом. В каждом графе наибольшее число рёберно непересекающихся разрезов, разделяющих вершины $u$ и $v$, равно наименьшему числу рёбер простой цепи, соединяющей $u$ и $v$, т. е. расстоянию $d(u,v)$ между $u$ и $v$.