Teorema

Se $G$ é um grafo não trivial, então $$\kappa (G) \leq_{(i)} \lambda(G) \leq_{(ii)} \delta(G)$$ onde:

• $\kappa (G)$ é a $k$-conexidade de $G$;
• $\lambda(G)$ é a aresta-conectividade de $G$;
• $\delta(G)$ é o grau mínimo de $G$.

Demonstração: A segunda desigualdade $(ii)$ decorre do fato de que todas as arestas incidentes com um vértice fixo separam $G$, além de que todas as arestas que incidem no vértice de menor grau (são no máximo $\delta(G)$), ao serem retiradas tornam o grafo desconexo.

Para a primeira desigualdade $(i)$ vamos tomar $F$ como o conjunto das $\lambda(G)$ arestas tais que $G-F$ é desconexo. Tal conjunto existe pela definição de $\lambda$. Observe que $F$ é um conjunto de arestas minimal separador em $G$. Mostremos que $\kappa(G) \leq |F|$.

Vamos agora supor que existe vértice $v$ que não é conectado por nenhuma aresta de $F$, e chamemos $C = G-F$ que contém $v$. Assim os vértices de $C$ que são conectados por uma aresta de $F$ separam $v$ de $G-C$. Uma vez que nenhuma aresta em $F$ tem ambas as extremidades em $C$(pela minimalidade de $F$),assim existem no máximo $|F|$ vértices, e portanto, conseguimos $\kappa (G) \leq |F|$, como desejado.

Supomos agora que todo vértice é conectado por uma aresta de $F$, tomemos $v$ como um vértice qualquer, e $C$ como descrito anteriormente, isto é, $C=G-F$ contendo $v$. Assim os vizinhos $w$ de $v$ com $wv \notin F$ tem conexão com alguma aresta de $F$, assim $d(v) \leq |F|$. Como $N(v)$ separa $v$ de outros vértices de $G$, implicando novamente que $\kappa (G) \leq |F|$, a menos que não tenham outros vértices, ou seja, a menos que $\{v\}\cup N(v) = G$, porém $v$ foi escolhido arbitrariamente, assim, assumindo que $G$ é completo, o caso mais “cheio” de arestas possíveis, temos que $\kappa (G) = \lambda(G) = |G| - 1$, seguindo o resultado.

$\square$