Teorema de Menger
# Teorema de Menger

Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo Teorema do Fluxo Máximo–Corte Mínimo.
A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma:
    G é um grafo finito não direcionado e x e y são dois vértices distintos. Então o teorema afirma que o tamanho mínimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-independentes emparelhados de x para y.
    Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é idêntico aos subgrafo maximal com um número mínimo de k caminhos aresta-independente entre qualquer par de nós x, y no subgrafo.
A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma:
    G é um grafo finito não direcionado e x e y são dois vértices não adjacentes. Então o teorema afirma que o número mínimo de vértices que precisam ser removidos para desconectar x e y é igual ao número máximo de caminhos vértice-independentes emparelhados de x para y.
    Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-vértices de corte é identico aos subgrafo maximal com um número mínimo de k caminhos vértice-independente entre qualquer par de nós x, y no subgrafo.

## Grafos infinitos

O teorema de Menger é valido para grafos infinitos, e nesse contexto se aplica ao corte mínimo entre quaisquer dois elementos que ou são vértices ou extremidades do grafo (Halin 1974). O resultado a seguir é um resultado de Ron Aharoni e Eli Berger e foi originalmente uma conjectura proposta por Paul Erdős, e antes de ser provada ficou conhecida como A conjectura Erdős–Menger. É equivalente ao teorema de Menger quando o grafo é finito.
    A e B são conjunto de vértices em um (possivelmente infinito) digrafo G. Então existe uma família P de A-B-caminhos disjuntos e um conjunto separador de exatamente um vértice para cada caminho em P.