Grafos e Subgrafos $2$-conexos
Anteriormente definimos o que é um grafo $k$-conexo. Aqui, nos preocuparemos com grafos $2$-conexos. Uma vez que o $k = 2$ é pequeno, podemos observar como tais grafos são construídos numa tentativa de melhor entender a intuição presente na definição de conexidade.
Definição
Um $G$ grafo $2$-conexo é um grafo conexo que continua conexo mesmo se retirarmos um vértice qualquer. Ou seja, precisamos remover pelo menos $2$ vértices para que $G$ deixe de ser conexo.
Grafos $2$-conexos também podem ser chamados de biconexos.
Abaixo vemos alguns grafos. Os dois primeiros são $2$-conexos, enquanto que o terceiro não.
Vale notar que os grafos $2$-conexos mais simples são os ciclos. Todos os outros podem ser construídos indutivamente adicionando caminhos a um ciclo.
Proposição
Um grafo $G$ é $2$-conexo se, e somente se, pode ser construído a partir de um ciclo adicionando sucessivamente $H$-caminhos com $H$ subgrafos definidos previamente.
Demonstração:
($\Rightarrow$) Basta notarmos que um grafo construído a partir de um ciclo é uma única componente conexa, e nenhum de seus vértices possui grau menor que $2$. Desse modo, nenhum de seus vértices é um vértice de corte (cutvertex); também chamado de vértice separador.
($\Leftarrow$) Seja $G$ um grafo $2$-conexo qualquer. Sabemos que $G$ contém um ciclo — pois quaisquer dois vértices podem ser ligados por caminhos disjuntos, e a união desses dois caminhos forma um ciclo. Então, possui um subgrafo $H$ maximal que pode ser construído como na hipótese. Posto que qualquer aresta $xy \in A(G) \setminus A(H)$, com $x, y \in H$, definiria um $H$-caminho, podemos concluir que $H$ é um subgrafo induzido de $G$. Suponhamos $H \neq G$. Pela conexidade de $G$, podemos encontrar uma aresta com uma extremidade em $H$ e uma fora dele, isto é, existe um $vw$ com $v \in G - H$ e $w \in H$. Agora, pela $2$-conexidade de $G$, podemos dizer que $G - w$ contém um caminho $P = vH$.
Disso decorre decorre que $wP$ é um $H$-caminho, e $H' = H \cup wP$ é um subgrafo maior que $H$ também construído da forma definida anteriormente. Chegamos numa contradição pela maximalidade de $H$, ou seja, $H = G$. Concluímos que $G$ pode ser construído adicionando sucessivos $H$-caminhos a um ciclo.
Lema 1
Seja $G$, um grafo qualquer. Então, vale o seguinte:
$(i)$ Os ciclos de $G$ são os ciclos de seus blocos;
$(ii)$ Os bonds de $G$ são os cortes minimais de seus blocos.
Demonstração:
$(i)$ Qualquer ciclo de $G$ é um subgrafo conexo sem vértice de corte, então está contido em algum bloco de $G$.
$(ii)$ Considere um corte qualquer de $G$. Se $xy$ é uma de suas arestas e $B$ é o bloco que o contém, pela maximalidade de $B$ não existe um $B$-caminho em $G$. Portanto, todo $x-y$ caminho de $G$ está contido em $B$, então quaisquer arestas que separam $x$ e $y$ em $B$ também o fazem em $G$.
$\square$
Lema 2
Seja $G$ um grafo qualquer e $ab,cd \in a(G)$. São equivalentes:
$(i)$ $ab$ e $cd$ pertencem a um mesmo bloco de $G$;
$(ii)$ $ab$ e $cd$ pertencem a um mesmo ciclo de $G$;
$(iii)$ $ab$ e $cd$ pertencem a um mesmo Bonds de $G$.
Demonstração: Primeiramente note que estaremos trabalhando com blocos de 3 (caso $b=c$ por exemplo) ou mais vértices, visto que supomos que ele possui ao menos duas arestas, sendo assim, o bloco em questão há de ser um subgrafo 2-conexo maximal e não uma ponte, nem um ponto isolado.
$(i) \Rightarrow (ii)$ Para isso, basta notar que em um grafo $2$-conexo, quaisquer dois pares de vértices podem ser ligados por dois caminhos disjuntos. Note que isso decorre da Proposição 1.
$(ii) \Rightarrow (iii)$ $C \subseteq G$ ciclo e $ab,cd\in E(C)$. Se deletarmos $ab$ e $cd$, separamos os vértices de $C$ em duas componentes conexas (de $C$), estendendo este ciclo para duas componentes conexas com outros vértices de $G$ na componente conexa onde $C$ está, temos que as arestas que ligam as componentes com $ab$ e $cd$ formam um bond.
$(iii) \Rightarrow (i)$ O item (ii) do Lema atesta esta implicação. Mais precisamente, diz que duas arestas podem estar no mesmo bond somente se estão no mesmo bloco, já que os bonds são os cortes minimais de um bloco.
$\square$
Nosso último lema sobre blocos mostra que eles se encaixam para formar a estrutura grosseira de $G$. Seja $\mathcal{A}$ o conjunto de vértices cortados de $G$, e $\mathcal{B}$ o conjunto de seus blocos. Temos então um grafo bipartido natural em $\mathcal{A} \cup \mathcal{B}$ formado pelas arestas $aB$ com $a \in B$. Este bloco-grafo de $G$ é mostrado na seguinte figura.
Lema 3
O bloco-grafo de um grafo conexo é uma árvore.
Demonstração: Suponhamos que não seja uma árvore. Assim, o bloco-grafo de um grafo conexo $G$ deve: conter um ciclo ou ser desconexo. Pela definição de bloco-grafo sabemos que ele é constituído por vértices adjacentes a vértices separadores. Desse modo, não pode ser cíclico. Então, deve ser desconexo. Para que isso ocorra, deve haver (pelo menos) um vértice de corte que não faz parte de nenhum bloco. Mas algum bloco devia conter esse vértice, ou não seria maximal. Caso não possa conter um desses vértices, então é porque ele faz parte de outra componente conexa, independente da que contém os blocos. Isso seria um absurdo, pois $G$ é conexo. Portanto, o bloco-grafo deve ser uma árvore.
$\square$