En teoría de grafos , el teorema de Berge establece que una coincidencia M en un grafo G es máxima (contiene el mayor número posible de aristas) si y solo si no existe un camino de aumento (un camino que comienza y termina en vértices libres (no coincidentes), y alterna entre aristas dentro y fuera de la coincidencia) con M.
Fue demostrado por el matemático francés Claude Berge en 1957 (aunque ya lo habían observado Petersen en 1891 y Kőnig en 1931).
Para demostrar el teorema de Berge, primero necesitamos un lema . Tomemos un grafo G y sean M y M ′ dos correspondencias en G . Sea G ′ el grafo resultante de tomar la diferencia simétrica de M y M ′ ; es decir ( M - M ′ ) ∪ ( M ′ - M ). G ′ constará de componentes conectados que son uno de los siguientes:
El lema se puede demostrar observando que cada vértice en G ′ puede ser incidente a lo sumo en 2 aristas: una desde M y otra desde M ′ . Los grafos donde cada vértice tiene grado menor o igual a 2 deben constar de vértices aislados , ciclos y caminos . Además, cada camino y ciclo en G ′ debe alternar entre M y M ′ . Para que un ciclo haga esto, debe tener un número igual de aristas desde M y M ′ , y por lo tanto ser de longitud uniforme.
Demostremos ahora el contrapositivo del teorema de Berge: G tiene una correspondencia mayor que M si y solo si G tiene un camino de aumento. Claramente, un camino de aumento P de G puede usarse para producir una correspondencia M ′ que sea mayor que M —solo tomemos M ′ como la diferencia simétrica de P y M ( M ′ contiene exactamente aquellas aristas de G que aparecen en exactamente uno de P y M ). Por lo tanto, se sigue la dirección inversa.
Para la dirección hacia adelante, sea M ′ un emparejamiento en G mayor que M . Considere D , la diferencia simétrica de M y M ′ . Observe que D consiste en caminos e incluso ciclos (como se observó en el lema anterior). Dado que M ′ es mayor que M , D contiene un componente que tiene más aristas de M ′ que M . Tal componente es un camino en G que comienza y termina con una arista de M ′ , por lo que es un camino de aumento.
Sea M un emparejamiento máximo y considérese una cadena alternada tal que las aristas en el camino alternan entre estar y no estar en M . Si la cadena alternada es un ciclo o un camino de longitud par que comienza en un vértice no emparejado, entonces se puede encontrar un nuevo emparejamiento máximo M ′ intercambiando las aristas que se encuentran en M y no en M . Por ejemplo, si la cadena alternada es ( m 1 , n 1 , m 2 , n 2 , ...), donde m i ∈ M y n i ∉ M , intercambiarlas haría que todos los n i fueran parte del nuevo emparejamiento y que todos los m i no fueran parte del emparejamiento.
Una arista se considera "libre" si pertenece a una coincidencia máxima pero no pertenece a todas las coincidencias máximas. Una arista e es libre si y solo si, en una coincidencia máxima arbitraria M , la arista e pertenece a un camino alterno par que comienza en un vértice no coincidente o en un ciclo alterno . Por el primer corolario, si la arista e es parte de tal cadena alterna, entonces debe existir una nueva coincidencia máxima, M ′ , y e existiría en M o M ′ , y por lo tanto sería libre. Por el contrario, si la arista e es libre, entonces e está en alguna coincidencia máxima M pero no en M ′ . Dado que e no es parte tanto de M como de M ′ , debe seguir existiendo después de tomar la diferencia simétrica de M y M ′ . La diferencia simétrica de M y M ′ da como resultado un grafo que consta de vértices aislados, ciclos alterno pares y caminos alternos. Supongamos, por el contrario, que e pertenece a algún componente de camino de longitud impar. Pero entonces uno de M y M ′ debe tener una arista menos que el otro en este componente, lo que significa que el componente en su conjunto es un camino de aumento con respecto a esa correspondencia. Por el lema original, entonces, esa correspondencia (ya sea M o M ′ ) no puede ser una correspondencia máxima, lo que contradice la suposición de que tanto M como M ′ son máximas. Por lo tanto, dado que e no puede pertenecer a ningún componente de camino de longitud impar, debe estar en un ciclo alterno o en un camino alterno de longitud par.