===== Uma relação de $k$-conexidade, $\ell$-aresta-conexidade e o grau mínimo de um grafo ===== === Teorema === //Se $G$ é um grafo não trivial, então $$\kappa (G) \leq_{(i)} \lambda(G) \leq_{(ii)} \delta(G)$$ onde:// * //$\kappa (G)$ é a [[.defKConexo|$k$-conexidade]] de $G$;// * //$\lambda(G)$ é a [[.defLarestaconex |aresta-conectividade]] de $G$;// * //$\delta(G)$ é o [[.grauMinimo| 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 [[.separategraph |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 [[.separar|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 [[.vizinhosDeV| vizinhos]] $w$ de $v$ com $wv \notin F$ tem conexão com alguma aresta de $F$, assim $d(v) \leq |F|$. Como [[.vizinhosDeV| $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$ é [[.defCompleto|completo]], o caso mais "cheio" de arestas possíveis, temos que $\kappa (G) = \lambda(G) = |G| - 1$, seguindo o resultado. $\square$ ---- === Leia Também === * [[.connectivity| Conectividade]].