En la disciplina matemática de la teoría de grafos, la fórmula de Tutte-Berge es una caracterización del tamaño de un emparejamiento máximo en un grafo . Es una generalización del teorema de Tutte sobre emparejamientos perfectos y recibe su nombre en honor a WT Tutte (quien demostró el teorema de Tutte) y Claude Berge (quien demostró su generalización).
El teorema establece que el tamaño de una coincidencia máxima de un gráfico es igual a donde cuenta cuántos de los componentes conectados del gráfico tienen un número impar de vértices.
De manera equivalente, el número de vértices no coincidentes en una coincidencia máxima es igual a
.
Intuitivamente, para cualquier subconjunto de los vértices, la única manera de cubrir completamente un componente impar de mediante una coincidencia es que una de las aristas coincidentes que cubren el componente incida en . Si, en cambio, algún componente impar no tuviera ninguna arista coincidente que lo conectara con , entonces la parte de la coincidencia que cubriera el componente cubriría sus vértices en pares, pero dado que el componente tiene un número impar de vértices, necesariamente incluiría al menos un vértice sobrante y no coincidente. Por lo tanto, si alguna elección de tiene pocos vértices pero su eliminación crea una gran cantidad de componentes impares, entonces habrá muchos vértices no coincidentes, lo que implica que la coincidencia en sí será pequeña. Este razonamiento se puede hacer preciso al afirmar que el tamaño de una coincidencia máxima es como máximo igual al valor dado por la fórmula de Tutte-Berge.
La caracterización de Tutte y Berge demuestra que este es el único obstáculo para crear un gran emparejamiento: el tamaño del emparejamiento óptimo estará determinado por el subconjunto con la mayor diferencia entre sus números de componentes impares externos y vértices internos . Es decir, siempre existe un subconjunto tal que al eliminar se crea el número correcto de componentes impares necesarios para que la fórmula sea verdadera. Una forma de encontrar dicho conjunto es elegir cualquier emparejamiento máximo y dejar que sea el conjunto de vértices que no tienen emparejamiento en , o que se pueden alcanzar desde un vértice no emparejado por un camino alterno que termina con una arista coincidente. Luego, sea el conjunto de vértices que coinciden con a vértices en . No pueden haber dos vértices en adyacentes, porque si lo fueran, sus caminos alternos podrían concatenarse para dar un camino por el cual se podría aumentar el emparejamiento, contradiciendo la maximalidad de . Cada vecino de un vértice en debe pertenecer a , de lo contrario podríamos extender un camino alterno a por un par más de aristas, a través del vecino, haciendo que el vecino se vuelva parte de . Por lo tanto, en , cada vértice de forma un componente de un solo vértice, que es impar. No puede haber otros componentes impares, porque todos los demás vértices permanecen coincidentes después de eliminar . Entonces, con esta construcción, el tamaño de y la cantidad de componentes impares creados al eliminar son los que deben ser para que la fórmula sea verdadera.
El teorema de Tutte caracteriza a los grafos con emparejamientos perfectos como aquellos para los cuales la eliminación de cualquier subconjunto de vértices crea como máximo componentes impares. (Un subconjunto que crea como máximo componentes impares siempre se puede encontrar en el conjunto vacío ). En este caso, por la fórmula de Tutte-Berge, el tamaño del emparejamiento es ; es decir, el emparejamiento máximo es un emparejamiento perfecto. Por lo tanto, el teorema de Tutte puede derivarse como un corolario de la fórmula de Tutte-Berge, y la fórmula puede verse como una generalización del teorema de Tutte.
