Vimos exemplos de gráficos conectados e gráficos que não estão conectados. Enquanto “não conectado” é praticamente um beco sem saída, há muito a ser dito sobre “como conectado” um gráfico conectado é. A abordagem mais simples é olhar o quão difícil é desconectar o agraph removendo vértices ou bordas. Nós assumimos que todos os gráficos são aresimples.
Se é possível desconectar um gráfico removendo um único vértice, chamado de ponto de corte, dizemos que o gráfico tem conectividade1. Se isto não for possível, mas é possível desconectar o gráfico removendo dois vértices, o gráfico tem conectividade 2.
Fazemos o mesmo para bordas:
Teorema 5.7.3 $\kappa(G)\le\lambda(G)$.
Gráficos que são 2-conectados são particularmente importantes, e o seguinte teorema simples é útil.
Existem outras simpáticas caracterizações de gráficos 2-conectados.
O seguinte corolário é uma fácil reafirmação deste teorema.
Esta versão do teorema sugere uma generalização:
Primeiro provamos a versão original do Menger, uma versão “local”.
Theorem 5.7.9 Se $v$ e $w$ são vértices não-adjacentes em $G$, $\kappa_G(v,w)=p_G(v,w)$.
>
Retornamos brevemente a 2-conectividade. O próximo teorema pode, às vezes, ser usado para fornecer a etapa de indução em uma prova de indução.
Um gráfico que não está conectado consiste em componentes conectados. No atheorem lembrando isto, vemos que gráficos conectados que não estão conectados2 são construídos a partir de subgrafos e pontes conectadas.
Definição 5.7.11 Um bloco em um gráfico $G$ é um subgrafo maximalinduzido em pelo menos dois vértices sem um ponto de corte.
Como de costume, o máximo aqui significa que o subgrafo induzido $B$ não pode ser maior pela adição de vértices ou arestas (enquanto mantém a propriedade desejada, neste caso, sem pontos de corte). Blocos são úteis em grande parte por causa deste teorema:
Teorema 5.7.12 Os blocos de $G$ dividem as arestas.
Se $G$ tem um único bloco, ou é $K_2$ ou é 2-conectado, e qualquer gráfico 2-conectado tem um único bloco.
Theorem 5.7.13 Se $G$ está ligado mas não ligado a 2, então cada vértice que está em dois blocos é um ponto de corte de $G$.
Exercícios 5.7
>
Ex 5.7.1Suponha um gráfico simples $G$ em $n\ge 2$ vértices tem pelo menos $$$d {(n-1)(n-2)}+1$ bordas. Prove que $G$ está conectado.
Ex 5.7.3Suponha que $G$ é simples com sequência de graus$d_1}le d_2_le}cdots_le d_n$, e para $k=le n-d_n-1$, $d_k=ge k$. Show$G$ está conectado.
Ex 5.7.4Recorde que um gráfico é $k$-regular se todos os vértices tiverem grau $k$. Qual é o menor número inteiro $k$ que faz isso ser verdade:
Se $G$ é simples, tem vértices $n$, $m\ge k$, e $G$ é $m$-regular,então $G$ está conectado.
(Claro que $k$ depende de $n$.)
Ex 5.7.6Procure um gráfico simples com $\kappa(G)
Note que um ponto de corte está contido em pelo menos dois blocos, de modo que os vértices dependentes do gráfico do ponto de corte do bloco são blocos. Estes blocos são chamados de endblocks.
Ex 5.7.10Desenhar o gráfico do ponto de corte do bloco do gráfico abaixo.