Definição

Um grafo $G = (V, A)$ é dito $k$-conexo ($k\in\mathbb{N}$) se $|V|>k$ e $G - X$ é conexo para todo $X\subset V$ com $|X|<k$. Em outras palavras, não há dois vértices de $G$ separados por menos de $k$ outros vértices.

O maior inteiro $k$ para o qual $G$ é $k$-conexo é a conectividade de $G$, denotada por $\kappa(G)$.