En teoría de grafos , el teorema de Berge establece que una coincidencia M en un gráfico G es máxima (contiene el mayor número posible de aristas) si y sólo si no hay un camino creciente (un camino que comienza y termina en vértices libres (no coincidentes), y alterna entre aristas dentro y fuera del emparejamiento) con M .
Fue demostrado por el matemático francés Claude Berge en 1957 (aunque ya observado por Petersen en 1891 y Kőnig en 1931).
Para demostrar el teorema de Berge, primero necesitamos un lema . Tome una gráfica G y sean M y M ′ dos coincidencias en G . Sea G ′ la gráfica resultante de tomar la diferencia simétrica de M y M ′ ; es decir ( M - M ′ ) ∪ ( M ′ - M ). G ′ estará formado por componentes conectados que sean uno de los siguientes:
El lema se puede probar observando que cada vértice en G ′ puede incidir como máximo en 2 aristas: una de M y otra de M ′ . Los gráficos donde cada vértice tiene un grado menor o igual a 2 deben consistir en vértices , ciclos y caminos aislados . Además, cada camino y ciclo en G ′ debe alternar entre M y M ′ . Para que un ciclo haga esto, debe tener el mismo número de aristas de M y M ′ y, por lo tanto, tener una longitud uniforme.
Demostremos ahora la contrapositiva del teorema de Berge: G tiene una coincidencia mayor que M si y sólo si G tiene una trayectoria creciente. Claramente, se puede usar una ruta de aumento P de G para producir una coincidencia M ′ que sea mayor que M ; simplemente tome M ′ como la diferencia simétrica de P y M ( M ′ contiene exactamente aquellos bordes de G que aparecen exactamente en una de P y M ). Por tanto, se sigue la dirección inversa.
Para la dirección de avance, sea M ′ una coincidencia en G mayor que M . Considere D , la diferencia simétrica de M y M ′ . Observe que D consta de caminos e incluso ciclos (como se observa 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 creciente.
Sea M una coincidencia máxima y considere una cadena alterna tal que los bordes en el camino alternan entre estar y no estar en M. Si la cadena alterna es un ciclo o un camino de longitud par que comienza en un vértice no coincidente, entonces se puede encontrar una nueva coincidencia máxima M ′ intercambiando las aristas encontradas en M y no en M . Por ejemplo, si la cadena alterna es ( m 1 , n 1 , m 2 , n 2 , ...), donde m i ∈ M y n i ∉ M , intercambiarlos haría que todos los n i formen parte de la nueva coincidencia y hacer que todo m no forme parte del emparejamiento.
Una ventaja 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 sólo 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 a un ciclo alterno . Según el primer corolario, si el borde e es parte de dicha 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 el borde e está 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 ′ , aún debe existir después de tomar la diferencia simétrica de M y M ′ . La diferencia simétrica de M y M ′ da como resultado un gráfico que consta de vértices aislados, incluso ciclos alternos 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 un borde menos que el otro en este componente, lo que significa que el componente en su conjunto es un camino creciente con respecto a esa coincidencia. Entonces, según el lema original, esa coincidencia (ya sea M o M ′ ) no puede ser una coincidencia máxima, lo que contradice el supuesto de que tanto M como M ′ son máximos. Entonces, dado que e no puede pertenecer a ningún componente de trayectoria de longitud impar, debe estar en un ciclo alterno o en una trayectoria alterna de longitud par.