Please sign in to answer question.
http://umamao.com/questions/grafos-k-aresta-...rs/4c8906e179de4f1a200003d2
Por que não?
Um grafo \(G\) é k-aresta-conexo se \(G[E(G)-S]\) é conexo para todo \(S \in E(G)\) com \(|S| < k\).
Se algum \(v \in V(G)\) for maior a \(k\), então vai existir um S tal que \(G[E(G)-S]\) não desconecta o grafo...
Pelo que você escreveu, isso é só uma implicação, então acho que um grafo (k+1)-aresta-conexo é, sim, k-aresta-conexo também.
Uma definição que encontrei de grafo k-aresta-conexo é "\(G\) é \(k\)-aresta-conexo se e só se cada par de vértices é ligado por \(k\) ou mais caminhos sem arestas em comum".
Ou seja, só há um limite inferior para o número de caminhos, então arestas a mais não são um problema.
Além disso, mesmo que \(\kappa'(G) = k\), isso não garante que algum vértice tenha grau \(k\). Um exemplo seria um grafo \(G\) com duas cliques grandes e somente uma aresta ligando as duas. Temos que \(\kappa'(G) = 1\) enquanto \(\delta(G)\) pode ser arbitrariamente grande.
Grafos k-aresta-conexos
Se um grafo e k-aresta-conexo, eu posso garantir que o grau de todos os vertices é \(d(k)\)?
Meu argumento é que a remoção de \(k-1\) arestas não vão desconectar o grafo... Vou precisar que o tamnho de S seja k, tal que \(G-S\) seja desconexo...
MC878 (Unicamp)
MO405 (Unicamp)
Grafos
Add Done