En la disciplina matemática de la teoría de grafos, el teorema de Tutte , que lleva el nombre de William Thomas Tutte , es una caracterización de gráficos con coincidencias perfectas . Es una generalización del teorema del matrimonio de Hall de gráficos bipartitos a gráficos arbitrarios. [ aclaración necesaria ] Es un caso especial de la fórmula de Tutte-Berge .
Nuestro objetivo es caracterizar todos los gráficos que no tienen una coincidencia perfecta. Comencemos con el caso más obvio de un gráfico sin una coincidencia perfecta: un gráfico con un número impar de vértices. En un gráfico de este tipo, cualquier coincidencia deja al menos un vértice no coincidente, por lo que no puede ser perfecto.
Un caso un poco más general es un gráfico desconectado en el que uno o más componentes tienen un número impar de vértices (incluso si el número total de vértices es par). Llamemos a estos componentes componentes impares . En cualquier coincidencia, cada vértice solo se puede hacer coincidir con los vértices del mismo componente. Por lo tanto, cualquier coincidencia deja al menos un vértice no coincidente en cada componente impar, por lo que no puede ser perfecto.
Luego, considere una gráfica G con un vértice u tal que, si quitamos de G el vértice u y sus bordes adyacentes, la gráfica restante (denotada G - u ) tiene dos o más componentes impares. Como arriba, cualquier coincidencia deja, en cada componente impar, al menos un vértice que no coincide con otros vértices en el mismo componente. Tal vértice solo puede coincidir con u . Pero como hay dos o más vértices no coincidentes, y solo uno de ellos puede coincidir con u , al menos otro vértice permanece sin coincidencia, por lo que la coincidencia no es perfecta.
Finalmente, considere un gráfico G con un conjunto de vértices U tal que, si quitamos de G los vértices en U y todos los bordes adyacentes a ellos, el gráfico restante (denotado G - U ) tiene más de | U | componentes extraños. Como se explicó anteriormente, cualquier coincidencia deja al menos un vértice no coincidente en cada componente impar, y estos pueden coincidir solo con los vértices de U , pero no hay suficientes vértices en U para todos estos vértices no coincidentes, por lo que la coincidencia no es perfecta.
Hemos llegado a una condición necesaria : si G tiene una correspondencia perfecta, entonces para cada subconjunto de vértices U en G , el gráfico G - U tiene como máximo | U | componentes extraños.