Teorema de Menger

Sejam $G$ um grafo e $A, B\subset V$. Então o número mínimo de vértices separando $A$ e $B$ em $G$ é igual ao número máximo de $A-B$ caminhos disjuntos em $G$.

Demonstração:

Seja $k$ o número mínimo de vértices separando $A$ e $B$. Veja que, dado um conjunto de $A-B$ caminhos disjuntos, um $A-B$ separador deve conter ao menos um vértice de cada caminho, logo, não podem haver mais que $k$ tais caminhos disjuntos. Assim, basta provar a existência de pelo menos $k$, o que pode ser feito utilizando indução em $||G||$, como mostramos a seguir:

Se $G$ não possui arestas, então $k = |A\cap B|$, e cada vértice de $A\cap B$ é um $A-B$ caminho (trivial) disjunto dos demais, logo, a afirmação vale.

Caso contrário, seja $e = xy\in A(G)$. Em $G/e$, seja $v_e$ o vértice resultante da contração da aresta $e$. Considere os conjuntos $A', B'$ de vértices de $G/e$ obtidos de $A, B$, respectivamente, ao trocarmos $x, y$ por $v_e$. Note que $A'-B'$ caminhos disjuntos em $G/e$ geram $A-B$ caminhos disjuntos em $G$, de modo que, se $G$ não possui $k$ $A-B$ caminhos disjuntos, então $G/e$ não possui $k$ $A'-B'$ caminhos disjuntos. Pela hipótese de indução, $G/e$ contém um $A-B$ separador de tamanho menor que $k$, digamos $Y$. É claro que $v_e$ deve pertencer a $Y$, pois, caso contrário, $Y$ seria $A-B$ separador em $G$. Então $X = (Y-\{e\})\cup \{x, y\}$ é um $A-B$ separador de no máximo $k$ vértices (pois possui um único elemento a mais que $Y$). Como $G$ não possui $A-B$ separadores de tamanho menor que $k$, segue que $X$ tem tamanho exatamente $k$.

Consideramos agora o grafo $G-e$. Como $x, y\in S$, todo $A-X$ separador em $G-e$ é $A-B$ separador em $G$, portanto, tem pelo menos $k$ vértices. Dessa forma, pela hipótese de indução, existem $k$ $A-X$ caminhos disjuntos. De modo análogo, existem $k$ $B-X$ caminhos disjuntos. Como $X$ separa $A$ e $B$, os $A-X$ caminhos e os $B-X$ caminhos não se encontram fora de $X$, logo, como $X$ tem exatamente $k$ elementos, podem ser combinados de modo a formar $k$ $A-B$ caminhos disjuntos, como queríamos.

Corolário 1

Sejam $B\subset V$ e $a\in V\setminus B$, então o mínimo de vértices separando $a$ de $B$ em $G$ é igual ao máximo de caminhos em um $a-B$ ventilador em $G$.

Demonstração:

Basta aplicar o Teorema de Menger a $G-a$, com $A:=N_G(a)$.

$\square$

Corolário 2

Sejam $a,b$ dois vértices distintos de $G$.

$(i)$ Se $ab\not\in E$, então o mínimo de vértices separando $a$ de $b$ em $G$ é igual ao máximo de $a-b$ caminhos independentes em $G$.

$(ii)$ O mínimo de arestas separando $a$ de $b$ em $G$ é igual ao máximo de $a-b$ caminhos disjuntos em arestas em $G$.

Prova:

$(i)$ Basta aplicar o Teorema de Menger a $G-\{a,b\}$, com $A:=N_G(a)$ e $B:=N_G(b)$.

$(ii)$ Bata aplicar o Teorema de Menger ao grafo das arestas de $G$, com $A:=E(a)$ e $B:=E(b)$.

$\square$

Teorema de Menger Global

$(i)$ Um grafo é $k$-conexo se, e somente se, contém $k$ caminhos independentes entre quaisquer dois vértices.

$(ii)$ Um grafo é $k$-conexo em arestas se, e somente se, contém $k$ caminhos disjuntos em arestas entre quaisquer dois vértices.

Demonstração:

$(i)$ $(\Leftarrow)$ Se um grafo $G$ contém $k$ caminhos independentes entre quaisquer dois vértices, então $\vert G\vert>k$ e $G$ não pode ser desconectado ao remover menos do que $k$ vértices.

$(\Rightarrow)$ Suponha $G$ $k$-conexo (em particular $\vert G\vert>k$) contendo vértices $a,b$ não ligados por $k$ caminhos independentes. Pelo Corolário 2 $(i)$, $a$ e $b$ são adjacentes. Seja $G':=G-ab$, então $G'$ contém no máximo $k-2$ $a-b$ caminhos independentes. Novamente pelo Corolário 2 $(i)$, existe um conjunto $X$ de no máximo $k-2$ vértices que separa $a$ de $b$ em $G'$. Como $\vert G\vert>k$, existe um vértice $v\in G\setminus(X\cup\{a,b\})$. Disso $X$ separa $v$ de $a$ ou $b$ em $G'$, digamos $a$. Mas então $X\cup\{b\}$ é um conjunto de $k-1$ vértices que separa $v$ de $a$ em $G$, contradizendo a $k$-conexidade de $G$.

$(ii)$ Segue do Corolário 2 $(ii)$.

$\square$